首页 > 代码库 > 子树路径

子树路径

题目连接: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\n",ans[i]);
70     }
71 }

 

子树路径