金币

第一行一个整数 n(2≤n≤10⁶)。表示森林中的点的个数。
第二行包含一个由 n 个数组成的序列（每个数保证在 0 到 n 之间）。序列中的第 i 个数表示第 i 个点的父亲。特别地，当数列中的一个数 p_i=0时，则说明它是森林中某一棵树的根。

一行若干个整数，表示在每棵树的树根处能捡到的金币枚数（请按输入顺序输出每一个树根的答案，即若有很多棵树，请按输入的顺序依次输出每一个树根的答案）。

C++14(g++5.4) 解法, 执行用时: 164ms, 内存消耗: 8288K, 提交时间: 2019-11-22 22:25:10

#include<bits/stdc++.h>
using namespace std;

int H,brother[1000005],son[1000005],D[1000005];
vector<int>R;
void dfs(int x,int h)
{
	H=max(H,h);
	D[h]++;
	if(brother[x])dfs(brother[x],h);
	if(son[x])dfs(son[x],h+1);
	return;
}
int main()
{
	int i,j,s,n;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&j);
		brother[i]=son[j];
		if(j)son[j]=i;
		else R.push_back(i); 
	}
	for(i=0;i<R.size();i++)
	{
		H=s=0,dfs(R[i],1);
		for(j=1;j<=H;j++)s+=(D[j]&1),D[j]=0;
		if(i)printf(" ");
		printf("%d",s);
	}
	printf("\n");
	return 0;
}

C++ 解法, 执行用时: 118ms, 内存消耗: 16024K, 提交时间: 2022-06-04 15:44:21

#include<cstdio>
using namespace std;
int k,n,ans,y;
int fa[1000005],h[1000005],b[1000005];
struct AB{
	int e,n;
}a[1000005];
void add(int u,int v){
	a[++k].e=v,a[k].n=h[u],h[u]=k;
}
void dfs(int x,int d){
	b[d]^=1;
	if(b[d] == 1) ++ans;
	else --ans;
	if(d > y) y=d;
	for(int i=h[x];i;i=a[i].n){
		dfs(a[i].e,d+1);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&fa[i]);
		add(fa[i],i);
	}
	for(int i=1;i<=n;i++){
		ans=0;
		if(!fa[i]) dfs(i,++y),printf("%d ",ans);	
	}
	return 0;
}

详情