题目传送门https://vjudge.net/problem/CSES-1674

解题思路

其实就是求每个子树的大小。

代码

#include<bits/stdc++.h>
using namespace std;int n;
vector<int> g[200001];
int sz[200001];
void dfs(int x,int fa)
{sz[x]=1;for(auto y:g[x]){if(y!=fa){dfs(y,x);sz[x]+=sz[y];}}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;int u,v;for(int i=2;i<=n;i++){cin>>u;g[i].push_back(u);g[u].push_back(i);}dfs(1,1);for(int i=1;i<=n;i++)cout<<sz[i]-1<<" ";return 0;
}