题目连接：https://scut.online/problem.php?id=90
维护每个节点的最长和次长路
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=100010; 6 7 int md1[maxn],md2[maxn]; //最长、次长 8 int ans[maxn]; // 9 10 struct node 11 { 12 int v; 13 int nex; 14 }e[maxn*2]; 15 16 17 int head[maxn]; 18 int cnt; 19 20 void add(int u,int v) 21 { 22 e[cnt].v=v; 23 e[cnt].nex=head[u]; 24 head[u]=cnt++; 25 } 26 27 int dfs(int u,int pre) 28 { 29 int d; 30 for(int i=head[u];i!=-1;i=e[i].nex) 31 { 32 if(e[i].v==pre) continue; 33 d=dfs(e[i].v,u)+1; 34 ans[u]=max(ans[u],ans[e[i].v]); // 35 if(d>md1[u]) 36 { 37 md2[u]=md1[u]; 38 md1[u]=d; 39 } 40 else if(d>md2[u]) md2[u]=d; 41 } 42 ans[u]=max(ans[u],md1[u]+md2[u]); // 43 return md1[u]; 44 45 } 46 int main() 47 { 48 int n; 49 int t; 50 scanf("%d",&t); 51 while(t--) 52 { 53 54 scanf("%d",&n); 55 cnt=0; 56 int u,v; 57 memset(head,-1,sizeof(head)); 58 memset(md1,0,sizeof(md1)); 59 memset(md2,0,sizeof(md2)); 60 memset(ans,0,sizeof(ans)); 61 for(int i=1;i<n;i++) 62 { - 63 scanf("%d%d",&u,&v); 64 add(u,v); 65 add(v,u); 66 } 67 dfs(1,0); 68 for(int i=1;i<=n;i++) 69 printf("%d ",ans[i]); 70 } 71 }