[COCI2017-2018 Contest5] Birokracija
题目描述
Mirko has become CEO of a huge corporation. This corporation consists of N people, labeled from 1 to N , and Mirko is labeled 1. The corporation is structured so that each employee (except Mirko) has a boss, and we say that employee is an assistant to that boss. Each boss can have multiple assistants, but still reports to their boss. This holds for everyone except Mirko, who is at the top of the pyramid and doesn’t have a boss, but has his assistants.
When Mirko gets a task from the investors, he then delegates that task to his assistant with the minimal number. This assistant then delegates the task to their assistant with the minimal number, and this process repeats until the task is given to an unlucky person without an assistant, who then must do the task.
This is when the real problems begin. The person that did the task gets paid 1 coin, the boss of that person gets 2 coins, the boss of that person gets 3 coins, and so on, all the way to Mirko, who gets as many coins as there are people in this sequence. After that, the employee that really did the job realizes how unfair the system is and quits their job out of principle.
When it comes to doing the next task in the corporation, there is a person less, so maybe the paychecks are less, but the work must continue. Tasks are piling up, so the whole procedure (assigning a new task, doing it, dividing paychecks and the person doing the task quitting) repeats until Mirko is left alone in the corporation and does his first (also his last) task.
Of course, Mirko will have amassed quite a fortune until then, but he also wants to know how much money each of the employees earned.
输入输出格式
输入格式:
The first line of input contains the positive integer N (2 ≤ N ≤ 2· 10^5105 ), the number of employees (including Mirko).
The following line contains N- 1 positive integers a_2a2 , a_3a3 , a_4a4 , …, a_nan (1 ≤ a_iai < i ), where a_iai denotes the boss of employee i .
输出格式:
You must output a single line consisting of N numbers, the i^{th}ith number corresponding to the amount of money earned by the i^{th}ith employee.
输入输出样例
3
1 1
5 1 1
5
1 2 2 4
13 8 1 3 1
说明
In test cases worth 50% of total points, it will hold 2 ≤ N ≤ 5000.
Clarification of the second test case:
Mirko assigns the first task to employee 2, who then assigns it to employee 3, who then does it. For this, employee 3 gets 1 coin, employee 2 gets 2 coins, and employee 1 (Mirko) gets 3 coins. Employee 3 then quits.
Mirko assigns the second task to employee 2, who then assigns it to employee 4 (because employee 3 quit), who then assigns it to employee 5, who then does it. For this, employee 5 gets 1 coin, employee 4 gets 2 coins, employee 2 gets 3 coins, and employee 1 gets 4 coins. Employee 5 then quits.
The procedure is repeated for a total of 5 tasks.
In total, Mirko gets 13 coins, employee 2 gets 8, employee 4 gets 3, and employee 3 and 5 each get 1 coin.
考虑每个点对其父亲的贡献肯定是自身的答案再加上自身的size,所以一遍dfs就好了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define pb push_back
const int maxn=200005;
vector<int> g[maxn];
int siz[maxn],n,pre;
ll ans[maxn]; void dfs(int x){
siz[x]=1;
for(int i=g[x].size()-1,to;i>=0;i--){
to=g[x][i],dfs(to);
ans[x]+=ans[to],siz[x]+=siz[to];
}
ans[x]+=(ll)siz[x];
} int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++) scanf("%d",&pre),g[pre].pb(i); dfs(1); for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
puts("");
return 0;
}
最新文章
- C++中的数组
- 从 Microsoft SQL Server 迁移到 Oracle
- [NOIP2016-day1-T2]天天爱跑步running_题解
- HttpRuntime应用程序的运行时
- c#中的枚举
- JavaScript Source Map 详解
- Qt for Android 开发大坑123
- Model和ModelAndView
- C#中的函数式编程:递归与纯函数(二)
- Fliptile 翻格子游戏
- 转载 python实例手册
- JQUERY的属性进行操作
- sql xml 入门 (二)
- [LeetCode&;Python] Problem 661. Image Smoother
- express 错误处理
- redis主从集群搭建及容灾部署(哨兵sentinel)
- 【转】单片机中volatile定义的作用详解
- 给HTML初学者的三十条最佳实践
- mysql 数据表读锁机制详解
- Windows多线程编程入门