HDU 3452 Bonsai

HDU_3452

    设树整体的根为T，对于以i为根节点的一棵子树，f[i]表示断开这棵树中的叶子和T的联系所需的最小代价。要断开i这棵子树中的叶子和T的联系，那么就是要断开i的所有孩子为根的子树中的叶子和T的联系。这样对于i的任意一个孩子j，要么j的叶子本来就和i断开的联系，要么就断开i->j这条边，依据这一点就可以用dp自底向上求得每个f[i]了，f[T]即为最后结果。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXD 1010
#define MAXM 2010
#define INF 0x3f3f3f3f
int N, T, f[MAXD], first[MAXD], e, next[MAXM], v[MAXM], w[MAXM];
void add(int x, int y, int z)
{
    v[e] = y, w[e] = z;
    next[e] = first[x], first[x] = e ++;
}
void init()
{
    int i, x, y, z;
    memset(first, -1, sizeof(first[0]) * (N + 1)), e = 0;
    for(i = 1; i < N; i ++)
    {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z), add(y, x, z);
    }
}
void dfs(int cur, int fa)
{
    int i, flag = 0;
    f[cur] = 0;
    for(i = first[cur]; i != -1; i = next[i])
        if(v[i] != fa)
        {
            flag = 1;
            dfs(v[i], cur);
            f[cur] += std::min(w[i], f[v[i]]);
        }
    if(flag == 0) f[cur] = INF;
}
void solve()
{
    dfs(T, -1);
    printf("%d\n", f[T]);
}
int main()
{
    while(scanf("%d%d", &N, &T), N)
    {
        init();
        if(N == 1) printf("0\n");
        else solve();
    }
    return 0;
}