hdu 4607 Park Visitは木の直径を求めます。
13341 ワード
テーマリンク：http://acm.hdu.edu.cn/showproblem.php?pid=4607
Clire and her little friend、ykwd、artravelling in Shevcheck's Park！The park is beautiful-but large，indeed.N feature spots in the parkarararararare e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e pargs，and Clire istototired to visit t t a a them.Afterconsidededededededidididididididididididididididididididididididedededededededed d d ininininininininininininininininininine e e e e them.Aft them.Afttttttttttttttttttrancs at each feature spot！Clire wants to chose an entrance、and find a way of visit to minimize the distance she has to walk.For convence、we can assine the length of all paths are 1.
Clire is too tired.Can you help her？
子供たちは公園で遊んでいます。公園にはNの観光スポットがあります。今、子供たちはその中のkつの観光スポットを見学したいです。そして、歩く道が一番短いです。最短経路を求める
アルゴリズム解析：まずこれは無方向連結図であり、樹形構造のような形をしていることを知っている。もし公園に長い道があったら、kより大きい観光スポットの数が含まれています。この時、k-1の観光スポットを歩く一番短いルートはk-1です。k個がないなら、できるだけ少ない観光スポットを別の道にしたいです。これにより、木の直径を求めるということが考えられます。（ツリーの直径の証明についてはネットでもたくさんあります）
木の直径のアルゴリズムを求めます。木の直径は木の一番長い簡単な道を指します。
法を求めます：2回のBFS：先に選んで1つの起点BFSを選んで最も長い道の終点を探し当てて、更に終点からBFSを行って、第2回のBFSの探し当てる最も長い道はつまり木の直径です。
原理：起点をuとし、初めてBFSで見つけた終点vは木の直径の一つの端点である。
証明：1）uが直径上の点であれば、vは明らかに直径の終点である（vがそうでなければ、他の点wが必ず存在し、uからwまでの距離が長くなると、BFSがv矛盾を見つけたから）
2）uが直径上の点でないと、uからvは必ず木の直径と交差します。交点からvまでは必ず直径の後半です。vは直径の一つの端点です。だから、vからBFSを行って得られるのは直径の長さです。
Clire and her little friend、ykwd、artravelling in Shevcheck's Park！The park is beautiful-but large，indeed.N feature spots in the parkarararararare e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e pargs，and Clire istototired to visit t t a a them.Afterconsidededededededidididididididididididididididididididididididedededededededed d d ininininininininininininininininininine e e e e them.Aft them.Afttttttttttttttttttrancs at each feature spot！Clire wants to chose an entrance、and find a way of visit to minimize the distance she has to walk.For convence、we can assine the length of all paths are 1.
Clire is too tired.Can you help her？
子供たちは公園で遊んでいます。公園にはNの観光スポットがあります。今、子供たちはその中のkつの観光スポットを見学したいです。そして、歩く道が一番短いです。最短経路を求める
アルゴリズム解析：まずこれは無方向連結図であり、樹形構造のような形をしていることを知っている。もし公園に長い道があったら、kより大きい観光スポットの数が含まれています。この時、k-1の観光スポットを歩く一番短いルートはk-1です。k個がないなら、できるだけ少ない観光スポットを別の道にしたいです。これにより、木の直径を求めるということが考えられます。（ツリーの直径の証明についてはネットでもたくさんあります）
木の直径のアルゴリズムを求めます。木の直径は木の一番長い簡単な道を指します。
法を求めます：2回のBFS：先に選んで1つの起点BFSを選んで最も長い道の終点を探し当てて、更に終点からBFSを行って、第2回のBFSの探し当てる最も長い道はつまり木の直径です。
原理：起点をuとし、初めてBFSで見つけた終点vは木の直径の一つの端点である。
証明：1）uが直径上の点であれば、vは明らかに直径の終点である（vがそうでなければ、他の点wが必ず存在し、uからwまでの距離が長くなると、BFSがv矛盾を見つけたから）
2）uが直径上の点でないと、uからvは必ず木の直径と交差します。交点からvまでは必ず直径の後半です。vは直径の一つの端点です。だから、vからBFSを行って得られるのは直径の長さです。
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
",a-1);
85 else printf("%d
",maxlen-1+(a-maxlen)*2);
86 }
87 }
88 return 0;
89 }