DFS序求子树大小
2025-02-04 10:12:30
发布于：上海
14阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
vector<int> tr[10010];
int n;
int ans[10010];
int l[10010],r[10010]; //l表示第一次到达这个结点 r表示最后一次到达这个结点
//返回以u为根的子树的大小传给父节点
int start = 1;
void dfs(int u){
l[u] = start++;
for(int son:tr[u])dfs(son);
r[u] = start;
}
int main(){
cin>>n;
for(int i=2;i<=n;i++){
int fa;
cin>>fa;
tr[fa].push_back(i);
}
dfs(1);
for(int i=1;i<=n;i++)cout<<r[i]-l[i]<<endl;
return 0;
}
这里空空如也
有帮助，赞一个