查找节点
2025-02-04 13:45:41
发布于：上海
8阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
vector<int> tr[101000];
int n,t;
int h[101000],zishu[101000];//子树大小深度
//一次dfs求深度和子树大小
int dfs(int u,int fa,int dep){
h[u] = dep;
int size = 1;
for(int son:tr[u]){
if(son==fa)continue;
size+=dfs(son,u,dep+1);
}
zishu[u] = size;
return size;
}
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)tr[i].clear();//情况你上一次创建的树
for(int i=2;i<=n;i++){
int x,y;
cin>>x>>y;
tr[x].push_back(y);
tr[y].push_back(x);
}
dfs(1,-1,1);
for(int i=1;i<=n;i++)cout<<h[i]<<' '<<(n-zishu[i]+1)<<endl;
}
return 0;
}
这里空空如也
有帮助，赞一个