HDoj 4607 Park Visit【木の直径の応用は1本の木の中でk個の点を通って歩く最も短い距離を求めます】

Park Visit
Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2754    Accepted Submission(s): 1249
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
5), 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
   
   
   
   

 
題意:N個の点とN-1辺からなる図(図は連通して環がない)をあげます.各辺の距離は1です.図の中でk点を通るのに歩く最短距離を聞いてください.(起点任意選択)
ツリーの直径の適用.説明を簡単にするために、ツリーの直径をS-Tパスで表します.
構想:まずS-T経路の長さansを求めて、分類して討論します(私達はすでにこのS-T経路の上でans+1個の点があることを知っています)
一:k<=ans+1、直接この経路の上で任意に起点を選んで、最短距離はk-1です;
二:k>ans+1は、ans+1点を歩いても足りないことを示しています.しかし,この経路はツリーの直径であることが知られており,そのS−Tの2つの端点度数はいずれも1であり,これは端点がS−T経路上の点と直接エッジのみに接続されていることを示している.
第2のケースでは,k個の点を十分に歩くためには,S−T経路以外の点を選択するしかない.しかし、図は連通図でリングがないため、S-T経路以外の点は必ずS-T経路上の点と直接接続されている.図を解釈する
          
S —— 2 —— 3 —— 4 ——T
                      |          |
                      5         6
図のように、テーマが6点足りなければ、私たちはS-Tという経路を歩いた後、5点しか歩いていません.仕方なく、残りの点は経路外の点しか歩けません.図のように、歩くには往復(3->4->3など)し、最後にS-T経路に戻り、S-T経路を歩き続けることがわかります.これで少なくとも歩く必要があります(k-ans-1)*2+ans.
ACコード:

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAXN 100000+10
#define MAXM 200000+100
using namespace std;
struct Edge
{
    int from, to, val, next;
};
Edge edge[MAXM];
int head[MAXN], edgenum;
int dist[MAXN];
bool vis[MAXN];
int N, M;
int node;//   S-T  
int ans;//     
void init()
{
    edgenum = 0;
    memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int w)
{
    Edge E = {u, v, w, head[u]};
    edge[edgenum] = E;
    head[u] = edgenum++;
}
void getMap()
{
    int a, b;
    for(int i = 1; i < N; i++)
    {
        scanf("%d%d", &a, &b);
        addEdge(a, b, 1);
        addEdge(b, a, 1);
    }
}
void SPFA(int sx)
{
    queue<int> Q;
    memset(dist, 0, sizeof(dist));
    memset(vis, false, sizeof(vis));
    vis[sx] = true;
    ans = 0;
    node = sx;
    Q.push(sx);
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            Edge E = edge[i];
            if(!vis[E.to] && dist[E.to] < dist[u] + E.val)
            {
                vis[E.to] = true;
                dist[E.to] = dist[u] + E.val;
                if(dist[E.to] > ans)
                {
                    ans = dist[E.to];
                    node = E.to;
                }
                Q.push(E.to);
            }
        }
    }
}
void solve()
{
    SPFA(1);// S-T  
    SPFA(node);//    
    int k;
    for(int i = 0; i < M; i++)
    {
        scanf("%d", &k);
        if(k <= ans + 1)//     ans + 1  
            printf("%d
", k - 1);
        else
            printf("%d
", (k - ans - 1) * 2 + ans);
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &N, &M);
        init();
        getMap();
        solve();
    }
    return 0;
}