HDU 4607.Park Visit-树的直径(BFS版)+结论公式(乱推公式)-备忘(加油！)

Park Visit

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4814 Accepted Submission(s): 2100

Problem Description

Claire and her little friend, ykwd, are travelling in Shevchenko's Park! The park is beautiful - but large, indeed. N feature spots in the park are connected by exactly (N-1) undirected paths, and Claire is too tired to visit all of them. After consideration, she decides to visit only K spots among them. She takes out a map of the park, and luckily, finds that there're entrances at each feature spot! Claire wants to choose an entrance, and find a way of visit to minimize the distance she has to walk. For convenience, we can assume the length of all paths are 1.
Claire is too tired. Can you help her?

Input

An integer T(T≤20) will exist in the first line of input, indicating the number of test cases.
Each test case begins with two integers N and M(1≤N,M≤10⁵), which respectively denotes the number of nodes and queries.
The following (N-1) lines, each with a pair of integers (u,v), describe the tree edges.
The following M lines, each with an integer K(1≤K≤N), describe the queries.
The nodes are labeled from 1 to N.

Output

For each query, output the minimum walking distance, one per line.

Sample Input

1 4 2 3 2 1 2 4 2 2 4

Sample Output

1 4

Source

2013 Multi-University Training Contest 1

题意就是给你一棵树，然后让你求k个点走一遍最短的路程，因为每个节点都有出口，所以不用再返回来。k个点是随意取的，只要求最短路径就可以。

思路就是先求一下树的直径，假设树的直径走过的节点为x个，如果k比x小，直接ans为k-1，如果大的话，就是树的直径+(k-直径节点数)*2就可以了。

公式我是随便测了几个数据然后猜出来的。。。

写的时候树的直径的板子错了，所以wa了几次。

代码:

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<bitset>
  6 #include<cassert>
  7 #include<cctype>
  8 #include<cmath>
  9 #include<cstdlib>
 10 #include<ctime>
 11 #include<deque>
 12 #include<iomanip>
 13 #include<list>
 14 #include<map>
 15 #include<queue>
 16 #include<set>
 17 #include<stack>
 18 #include<vector>
 19 using namespace std;
 20 typedef long long ll;
 21 typedef long double ld;
 22 typedef pair<int,int> pii;
 23 
 24 const double PI=acos(-1.0);
 25 const double eps=1e-6;
 26 const ll mod=1e9+7;
 27 const int inf=0x3f3f3f3f;
 28 const int maxn=1e5+10;
 29 const int maxm=100+10;
 30 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 31 
 32 int n,m,cnt;//cnt为边数
 33 int dist[maxn],head[maxn];//dist表示最长路，head为存图用的
 34 bool vis[maxn];
 35 
 36 struct node{//定义边的结构体
 37     int from,to,val,next;
 38 }edge[maxn<<1];//注意是无向图，边数是二倍的
 39 
 40 void init()//初始化，不可少
 41 {
 42     cnt=0;
 43     memset(head,-1,sizeof(head));
 44 }
 45 
 46 void addedge(int u,int v,int w)
 47 {
 48     edge[cnt].from=u;//起点
 49     edge[cnt].to=v;//终点
 50     edge[cnt].val=w;//权值
 51     edge[cnt].next=head[u];//指向下一条边
 52     head[u]=cnt++;
 53 }
 54 
 55 int length;//最终的最长路径(树的直径)
 56 int node;//记录端点值
 57 
 58 void bfs(int s)
 59 {
 60     queue<int>q;//定义队列
 61     memset(vis,false,sizeof(vis));//初始化，清零
 62     memset(dist,0,sizeof(dist));
 63     q.push(s);//入列
 64     vis[s]=true;//记录为遍历过的点
 65     length=0;
 66     node=s;
 67     while(!q.empty()){
 68         int u=q.front();
 69         q.pop();
 70         for(int i=head[u];i!=-1;i=edge[i].next){//遍历每一条边
 71             int v=edge[i].to;
 72             if(!vis[v]&&dist[v]<dist[u]+edge[i].val){
 73                 vis[v]=true;
 74                 dist[v]=dist[u]+edge[i].val;//到v的最长路径
 75                 if(length<dist[v]){
 76                     length=dist[v];//不断更新最长路径
 77                     node=v;//更新节点
 78                 }
 79                 q.push(v);//重新入列，寻找下一个点
 80             }
 81         }
 82     }
 83 }
 84 
 85 int main()
 86 {
 87     int t;
 88     scanf("%d",&t);
 89     while(t--){
 90         init();
 91         scanf("%d%d",&n,&m);
 92         for(int i=1;i<n;i++){
 93             int u,v,val;
 94             scanf("%d%d",&u,&v);
 95             val=1;//路径权值
 96             addedge(u,v,val);
 97             addedge(v,u,val);
 98         }
 99         bfs(1);//第一遍找到距离最远的端点
100         bfs(node);//第二遍找最长距离
101         int x=length+1;//x为树的直径的节点个数
102         while(m--){
103             int k;
104             scanf("%d",&k);
105             if(k<=x) printf("%d
",k-1);//如果比树的直径短
106             else{
107                 int ans=length+(k-x)*2;
108                 printf("%d
",ans);
109             }
110         }
111     }
112     return 0;
113 }
114 
115 
116 /*
117 1
118 19 5
119 1 2
120 1 3
121 2 4
122 2 5
123 3 6
124 3 7
125 4 8
126 4 9
127 8 12
128 12 13
129 9 14
130 14 15
131 15 16
132 5 10
133 5 11
134 10 17
135 17 18
136 17 19
137 
138 7
139 6
140 
141 10
142 9
143 
144 11
145 11
146 
147 12
148 13
149 
150 15
151 19
152 
153 */

开溜，回寝室洗澡。。。