hdu 4607 Park Visit (dfs)

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

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

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <queue>

 #include <vector>

 #define maxn 105000

 using namespace std;

 const int INF = 0x3f3f3f;

 vector<int> G[maxn];

 int N,M;

 int maxdeep,point;

 bool vis[maxn];

 void dfs(int u,int deep){

     if(maxdeep < deep){

         maxdeep = deep;

         point = u;

     }

     for(int i=;i<G[u].size();i++){

        int v = G[u][i];

        if(!vis[v]){

          vis[v] = true;   //printf("u,v  %d %d\n",u,v);jf

          dfs(v,deep+);

        }

     }

 }

 int main()

 {

     //if(freopen("input.txt","r",stdin)== NULL)  {printf("Error\n"); exit(0);}

     int T;

     cin>>T;

     while(T--){

         cin>>N>>M;

         if(N == ){

             for(int i=;i<=M;i++){

                 int K;

              scanf("%d",&K);

              printf("0\n");

                }

             continue;

         }

         for(int i=;i<=N;i++)   G[i].clear();

         for(int i=;i<=N-;i++){

             int a,b;

             scanf("%d %d",&a,&b);

             G[a].push_back(b);

             G[b].push_back(a);

         }

         memset(vis,,sizeof(vis));

         maxdeep = ; point = ;

         vis[] = true;

         dfs(,);

         memset(vis,,sizeof(vis));

         dfs(point,);

         for(int i=;i<=M;i++){

             int K;

             scanf("%d",&K);

             if(maxdeep >= K-) printf("%d\n",K-);

             else           printf("%d\n",maxdeep +  * (K -  - maxdeep));

         }

     }

 }