loj 1412(树上最长直径的应用)

题目链接：http://lightoj.com/volume_showproblem.php?problem=1412

思路：好久没写题解了，有点手生，这题从昨天晚上wa到现在终于是过了。。。思想其实很简单，就是预处理出每一块的最长直径，然后每次询问的时候直接查询就可以了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 using namespace std;

 const int MAXN = ( + );

 typedef pair<int,int>Pair;

 vector<int >g[MAXN];

 vector<Pair >blocks;

 int n,m,q,len,_count,max_len;

 bool mark[MAXN];

 int dfs(int u,int father)

 {

     if(!mark[u])mark[u] = true, _count ++;

     int first = , second = ;

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

         int v = g[u][i];

         if(v == father)continue;

         int tmp = dfs(g[u][i],u) + ;

         if(tmp > first)second = first, first = tmp;

         else if(tmp > second)second = tmp;

     }

     if(first + second > len)len = first + second;

     return first;

 }

 int cmp(Pair p, Pair q)

 {

     if(p.second != q.second){

         return p.second > q.second;

     }else

         return p.first > q.first;

 }

 int main()

 {

     int u,v,_case,t=;

     scanf("%d",&_case);

     while(_case--){

         scanf("%d%d",&n,&m);

         for(int i=;i<=n;i++)g[i].clear();

         while(m--){

             scanf("%d%d",&u,&v);

             g[u].push_back(v);

             g[v].push_back(u);

         }

         len=;

         max_len = ;

         memset(mark,false,sizeof(mark));

         blocks.clear();

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

             if(!mark[i]){

                 len=;

                 _count = ;

                 dfs(i,-);

                 blocks.push_back(make_pair(len,_count));

                 max_len = max(max_len,len);

             }

         }

         sort(blocks.begin(),blocks.end(),cmp);

         scanf("%d",&q);

         printf("Case %d:\n",t++);

         while(q--){

             int k;

             scanf("%d",&k);

             if(k > blocks[].second){

                 puts("impossible");

             }else if(k <= max_len + ){

                 printf("%d\n",k - );

             }else {

                 int ans = ( << );

                 for(int i=; i<(int)blocks.size(); i++){

                     if(k > blocks[i].second)break;

                     ans = min (ans, (blocks[i].first)+*(k-blocks[i].first-));

                 }

                 printf("%d\n",ans);

             }

         }

     }

     return ;

 }