hdu 4607 Park Visit 求树的直径

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #define inf 0x7fffffff
 9 using namespace std;
10 const int maxn=100000+10;
11 const int M = 100000+10;
12 
13 int n,m;
14 struct node
15 {
16     int v,w;
17     int next;
18 }edge[M*3];
19 int head[maxn],edgenum;
20 
21 void add(int u,int v,int w)
22 {
23     edge[edgenum].v=v ;edge[edgenum].w=w ;
24     edge[edgenum].next=head[u] ;head[u]=edgenum++ ;
25 
26     edge[edgenum].v=u ;edge[edgenum].w=w ;
27     edge[edgenum].next=head[v] ;head[v]=edgenum++ ;
28 }
29 
30 int vis[maxn],d[maxn];
31 int bfs(int from)
32 {
33     queue<int> Q;
34     Q.push(from);
35     memset(d,-1,sizeof(d));
36     memset(vis,0,sizeof(vis));
37     d[from]=1;
38     vis[from]=1;
39     int maxlen=-1,k=0;
40     while (!Q.empty())
41     {
42         int u=Q.front() ;Q.pop() ;
43         for (int i=head[u] ;i!=-1 ;i=edge[i].next)
44         {
45             int v=edge[i].v;
46             if (!vis[v])
47             {
48                 vis[v]=1;
49                 d[v]=d[u]+1;
50                 if (d[v]>maxlen)
51                 {
52                     maxlen=d[v];
53                     k=v;
54                 }
55                 Q.push(v);
56             }
57         }
58     }
59     return k;
60 }
61 
62 int main()
63 {
64     int t;
65     scanf("%d",&t);
66     while (t--)
67     {
68         memset(head,-1,sizeof(head));
69         edgenum=0;
70         int a,b;
71         scanf("%d%d",&n,&m);
72         for (int i=1 ;i<=n-1 ;i++)
73         {
74             scanf("%d%d",&a,&b);
75             add(a,b,1);
76         }
77         int v=bfs(1);
78         int u=bfs(v);
79         int maxlen=d[u];
80         //cout<<"debug= "<<maxlen<<endl;
81         for (int i=0 ;i<m ;i++)
82         {
83             scanf("%d",&a);
84             if (a<=maxlen) printf("%d\n",a-1);
85             else printf("%d\n",maxlen-1+(a-maxlen)*2);
86         }
87     }
88     return 0;
89 }