【校赛】求树的各层结点的权值的平均值

关心员工（25）

Description

SLF是G市某集团的总裁，他认为能一起打拼的员工都是好兄弟，因此他十分关心公司各个层次员工的生活水平。在公司中，每位员工都有且只有一名直属上司（SLF除外），而上司有可能有多个下属员工，于是各级员工之间就有了层次之分。为了更好地给员工补贴，SLF会定期统计各层次员工的平均收入。由于SLF忙于处理集团事务，于是想请你帮忙编程解决这个问题。

Input

K   N_1   N_2  ...   N_K   SalaryK  N1​  N2​ ...  NK​  Salary输入第一行中给出一个整数N(1 \leq N \leq 10^5)N(1≤N≤105)，即整个公司的总人数，每个员工从1到N编号，总裁SLF的编号为1。随后N行，第i行给出编号为i的员工的相关信息，格式如下：

K   N_1   N_2  ...   N_K   SalaryK  N1​  N2​ ...  NK​  Salary

其中K是一个整数(0 \leq K \leq20)(0≤K≤20)，表示该员工直接下属员工的个数，N_iNi​是直接下属员工的编号，Salary是一个正数(Salary \leq 2*10^4)(Salary≤2∗104)，表示该员工的收入。

Output

在一行中对应输出公司的层次数m，随后m行中输出各层次员工的平均工资，格式为”Level i: average_iaveragei​”（不含双引号）,其中average_iaveragei​表示第i层员工的平均工资，需要保留两位小数。

Sample Input 1 

7
2 2 3 100
3 4 5 6 2
1 7 3
0 4
0 5
0 6
0 7
           

Sample Output 1

3
Level 1: 100.00
Level 2: 2.50
Level 3: 5.50
           

看这个题目时已经晚了。在20分以上的题，这道25分的题起码有些想法。特么我看着不会的题在那瞎想什么，不会基本上再纠结也是浪费时间。赛后敲了一下代码。

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

const int maxn=100005;
const int maxdepth=100005;  // 大小不确定，交了几次，发现要这么大才能AC

vector<int> g[maxn];
double w[maxn];
double sum[maxdepth]; 
int cnt[maxdepth];
int depth=-1;
int n;

// dfs(1, 1)
void dfs(int r, int level)
{
	sum[level]+=w[r];
	cnt[level]++;
	if(level>depth)
		depth=level;
	for(int i=0;i<g[r].size();i++)
		dfs(g[r][i], level+1);
}

int main()
{
	cin>>n;
	
	int i, j;
	for(i=1;i<=n;i++)
	{
		int cnt, t;
		cin>>cnt;
		for(j=0;j<cnt;j++)
		{
			cin>>t;
			g[i].push_back(t);
		}
		cin>>w[i];
	}
	dfs(1, 1);
	
	printf("%d\n", depth);
	for(i=1;i<=depth;i++)
		printf("Level %d: %.2lf\n", i, sum[i]/cnt[i]);
	
	return 0;
}