uva 12223(树形dp)

题意：一个城市有n个景点，景点和景点之间的路线形成一棵无根树(也就是有n-1条边)，给出景点之间的花费，一个人可以任选一个景点住在那里，然后他每年都要固定去m个景点，给出这m个景点和要去的次数，这个人每次去了景点都会回家，问他一年为了观赏景点最少花费多少钱。
题解：想了好久，看看题解才完全理解。要先把无根树转化成有根树，默认让1成为根节点，然后先dfs把每个节点v当做根节点的子树的节点数统计一下在num[v]中，因为计算u-v边的走到次数就是以v为根节点的子树的节点数的个数乘边的权值乘2(来回)，同时把f[1]也就是以1为根节点到想去的景点的花费得出(因为1没有父亲节点)，这个过程是自底向上的。
然后dp中更新其余n-1个点的f[v]值，f[v]和自己父亲节点u的f[u]有关，可以想到，如果把居住地从u变成了v，花费变化其实只有u-v这条边，只要得到通过u-v这边的新次数，就可以直接更新f[v]值了，这个更新过程是自顶向下的。
状态转移方程：f[v] = f[u] - num[v] * 2 * w + (num[1] - num[v]) * 2 * w。
先把u通过v到其他节点的次数减掉，然后把v通过u到其他节点的次数加起来。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 50005;
int n, m, vis[N];
vector<int> g[N];
vector<long long> w[N];
long long f[N], num[N], res;

void init() {
    memset(num, 0, sizeof(num));
    for (int i = 0; i <= n; i++) {
        g[i].clear();
        w[i].clear();
    }
}

void dp(int u) {
    vis[u] = 1;
    res = min(res, f[u]);
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        long long ww = w[u][i];
        if (vis[v])
            continue;
        f[v] = f[u] - num[v] * 2 * ww + (num[1] - num[v]) * 2 * ww;
        dp(v);
    }
}

void dfs(int u) {
    vis[u] = 1;
    f[u] = 0;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        long long ww = w[u][i];
        if (vis[v])
            continue;
        dfs(v);
        num[u] += num[v];
        f[u] += f[v] + num[v] * ww * 2;
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        init();
        int u, v;
        long long ww;
        for (int i = 0; i < n - 1; i++) {
            scanf("%d%d%lld", &u, &v, &ww);
            g[u].push_back(v);      
            g[v].push_back(u);      
            w[u].push_back(ww);
            w[v].push_back(ww);
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d%lld", &u, &ww);
            num[u] = ww;
        }
        memset(vis, 0, sizeof(vis));
        dfs(1);
        res = f[1];
        memset(vis, 0, sizeof(vis));
        dp(1);
        printf("%lld\n", res);
        int flag = 0;
        for (int i = 1; i <= n; i++) {
            if (f[i] == res && !flag) {
                printf("%d", i);
                flag = 1;
            }
            else if (f[i] == res)
                printf(" %d", i);
        }
        printf("\n");
    }
    return 0;
}