HDU_3452

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

#include
     
      #include
      
       #include
       
        #define MAXD 1010#define MAXM 2010#define INF 0x3f3f3f3fint 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;}