HDU 4607 树的直径

题意：每条边的长度是1，求访问k个节点，最少走多远。

分析：贪心，首先走直径len，走完直径len+1个点后，走剩下的点(k-len-1)，而走这些点最少一定为(k-len-1)*2。

证明：反证法，要是比(k-len-1)*2还短，那么之前的直径len，就不是直径了。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100000+5;

struct Edge {
    int v,c;
};

vector<Edge> G[maxn];

int len;
int tmp;
void dfs(int x,int fa,int dep) {
    if(dep>len) {
        tmp = x;
        len = dep;
    }
    for(int i=0;i<G[x].size();i++) {
        int v = G[x][i].v;
        int c = G[x][i].c;
        if(v==fa) continue;
        dfs(v,x,dep+c);
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--) {
    
        int n,m;
        scanf("%d%d",&n,&m);

        for(int i=0;i<=n;i++)
            G[i].clear();
        
        for(int i=0;i<n-1;i++) {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back((Edge){v,1});
            G[v].push_back((Edge){u,1});
        }

        len = -1;
        dfs(1,-1,0);
        int st = tmp;
        len = -1;
        dfs(st,-1,0);
        while(m--) {
            int k;
            scanf("%d",&k);
            if(k<=len+1)
                printf("%d
",k-1);
            else {
                printf("%d
",len+(k-len-1)*2);
            }
        }

    }

    return 0;
}