2694995_tle.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 52 行

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

using namespace std;

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

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]++;
	}
	que.push(0);
	while(!que.empty())
	{
		t = que.front();
		que.pop();
		for(i = 0; i < tree[t].size(); i++)
			que.push(tree[t][i]);
		ans += cal(deg[t]);
	}
	printf("%d\n",ans);
	return 0;
}