2695124_tle.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int n, d;
vector <int> tree[100001];
int deg[100001];
int que[100001];
int f, r;

int cal(int t)
{
	int ans = 0, tmp;

	while (t > d)
	{
		tmp = t/d;
		ans += tmp;
		t -= tmp*d;
		t += tmp;
	}
	return ans;
}

int main()
{
	int i, t, ans;

	ans = 0;
	scanf("%d%d",&n,&d);
	memset(deg,0,sizeof(deg));
	for(i = 1; i <= n; i++)
	{
		scanf("%d",&t);
		tree[t].push_back(i);
		deg[t]++;
	}
	f = r = -1;
	que[++r] = 0;
	while(f!=r)
	{
		++f;
		t = que[f];
		for(i = 0; i < tree[t].size(); i++)
			que[++r] = tree[t][i];
		ans += cal(deg[t]);
	}
	printf("%d\n",ans);
	return 0;
}