UVALive - 4614 Moving to Nuremberg(트리 DP)

제목: 나무 한 그루를 드릴게요. 일정한 횟수를 가야 할 때가 있어요. 갈 때마다 돌아와야 해요. 최소한의 권한과
사고방식: 먼저 뿌리가 없는 나무를 전환하면 뿌리가 있는 나무를 초기화한 다음에 뿌리에 대한 권한과 각 트리가 가야 할 횟수를 초기화한다. 그 다음에 가장 작은 권한과 dp[u]를 어떻게 구하는지, 그 하위 노드 v의 dp[v]를 어떻게 구하는지 알고 있다.
dp[v]=dp[u]+(sum-f[v])*len-len*f[v],sum는 전체 횟수를 표시하고,len은 (u,v)의 권치의 두 배로 부자 노드의 관계에 따라 내놓을 수 있다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 1000000000000000LL
using namespace std;
const int MAXN = 50010;

int n,m,num,cas,u,v;
long long ans,sum,w;
int head[MAXN],next[MAXN*2],ev[MAXN*2],temp[MAXN];
long long fre[MAXN],f[MAXN],ew[MAXN*2],dp[MAXN],dis[MAXN];

void addedge(int u,int v,long long w){
    next[++num] = head[u];
    head[u] = num;
    ev[num] = v;
    ew[num] = w;
}

void read(){
    memset(head,-1,sizeof(head));
    memset(fre,0,sizeof(fre));
    num = -1;
    scanf("%d",&n);
    for (int i = 0; i < n-1; i++){
        scanf("%d%d%lld",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }
    sum = 0;
    scanf("%d",&m);
    for (int i = 0; i < m; i++){
        scanf("%d%lld",&u,&w);
        fre[u] = w;
        sum += fre[u];
    }
}

void pre_dfs(int fa,int u){
    f[u] = 0;
    dis[u] = 0;
    for (int i = head[u]; i != -1; i = next[i])
        if (ev[i] != fa){
            pre_dfs(u,ev[i]);
            dis[u] += dis[ev[i]] + 2 * ew[i] * f[ev[i]];
            f[u] += f[ev[i]];
        }
    f[u] += fre[u];
}

void dfs(int fa,int u,long long dis){
    dp[u] = dis;
    if (dp[u] < ans)
        ans = dp[u];
    for (int i = head[u]; i != -1; i = next[i])
        if (fa != ev[i])
            dfs(u,ev[i],dis+2*ew[i]*(sum-2*f[ev[i]]));
}

void solve(){
    pre_dfs(1,1);
    ans = INF;
    dfs(1,1,dis[1]);
    printf("%lld
",ans);
    int cnt = -1;
    for (int i = 1; i <= n; i++)
        if (dp[i] == ans)
            temp[++cnt] = i;
    for (int i = 0; i <= cnt; i++)
        if (i != cnt)
            printf("%d ",temp[i]);
        else printf("%d
",temp[i]);
}

int main(){
    scanf("%d",&cas);
    while (cas--){
        read();
        solve();
    }
    return 0;
}