HDU4607(최대 지름 트리 DP)

제목은 나무 한 그루를 주고 한 점에서 출발하여 k점을 가며 적어도 몇 번은 가느냐고 묻는 것이다.
한 번의 트리 DP를 통해 최대 지름을 구하고 최대 지름이 k개의 점을 포함할 수 있다면 최대 지름으로 가세요. 그렇지 않으면 점을 추가할 때마다 한 변을 두 번 더 걸어야 해요. 그러면 답은 어렵지 않아요.

#include <bits/stdc++.h>
using namespace std;
#define maxn 511111
#define maxm 1111111

int dp[maxn][2]; // i                 
struct node {
    int to, next;
}edge[maxm];
int n, m, head[maxn], cnt;
int Max; //   

void add_edge (int from, int to, int i) {
    node &e = edge[i];
    e.to = to, e.next = head[from], head[from] = i;
}

void dfs (int u, int father) {
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v == father)
            continue;
        dfs (v, u);
        if (dp[v][0]+1 > dp[u][0]) {
            dp[u][1] = dp[u][0];
            dp[u][0] = dp[v][0]+1;
        }
        else if (dp[v][0]+1 > dp[u][1]) {
            dp[u][1] = dp[v][0]+1;
        }
    }
    Max = max (dp[u][1]+dp[u][0], Max);
}

int main () {
    //freopen ("in", "r", stdin);
    int t;
    scanf ("%d", &t);
    while (t--) {
        scanf ("%d%d", &n, &m);
        cnt = 0;
        memset (head, -1, sizeof head);
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf ("%d%d", &u, &v);
            add_edge (u, v, cnt++);
            add_edge (v, u, cnt++);
        }
        Max = 0;
        memset (dp, 0, sizeof dp);
        dfs (1, 0);
        int q;
        while (m--) {
            scanf ("%d", &q);
            //cin >> q;
            if (q <= Max+1) {
                printf ("%d
", q-1);
            }
            else {
                printf ("%d
", Max+2*(q-Max-1));
            }
        }
    }
    return 0;
}