hdu 4607 Park Visit (dfs)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4607

首先如果k小于等于直径长度，那么答案为k−1。如果k大于直径长度，设直径长度为r，那么答案为r−1+(k−r)∗2。

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <cstring>
 6 #include <queue>
 7 #include <vector>
 8 #define maxn 105000
 9 using namespace std;
10 
11 const int INF = 0x3f3f3f;
12 
13 vector<int> G[maxn];
14 int N,M;
15 int maxdeep,point;
16 bool vis[maxn];
17 void dfs(int u,int deep){
18     if(maxdeep < deep){
19         maxdeep = deep;
20         point = u;
21     }
22     for(int i=0;i<G[u].size();i++){
23        int v = G[u][i];  
24        if(!vis[v]){
25          vis[v] = true;   //printf("u,v  %d %d
",u,v);jf
26          dfs(v,deep+1);
27        }
28     }
29 }
30 
31 int main()
32 {
33     //if(freopen("input.txt","r",stdin)== NULL)  {printf("Error
"); exit(0);}
34 
35     int T;
36     cin>>T;
37     while(T--){
38         cin>>N>>M;
39         if(N == 1){
40             for(int i=1;i<=M;i++){
41                 int K;
42              scanf("%d",&K);
43              printf("0
");
44                } 
45             continue;       
46         } 
47           
48         for(int i=1;i<=N;i++)   G[i].clear();
49         for(int i=1;i<=N-1;i++){
50             int a,b;
51             scanf("%d %d",&a,&b);
52             G[a].push_back(b);
53             G[b].push_back(a);
54         }
55         memset(vis,0,sizeof(vis));
56         maxdeep = 0; point = 0;
57         vis[1] = true;
58         dfs(1,0);
59         memset(vis,0,sizeof(vis));
60         dfs(point,0);
61         for(int i=1;i<=M;i++){
62             int K;
63             scanf("%d",&K);
64             if(maxdeep >= K-1) printf("%d
",K-1);
65             else           printf("%d
",maxdeep + 2 * (K - 1 - maxdeep));
66         }
67     }
68 }

View Code