hdu 4118 Holiday's Accommodation

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp （树上的一些性质）

题意：将树上的每一个点移动到另一个点的位置（但不一定是两两点交换），每个点移动走过的距离累加起来得到一个和，使得这个和最大。

这题不是很想归类为树dp，因为主要不依靠父子关系来得到想要的信息，这题主要是根据题意来搞清楚一个性质并且证明它，那么就是一个很容易实现代码的题目了

性质：找任意一条边，都能将整个树分为两个部分，左部有m1个点，右部有m2个点，假设较小值为m1，那么在整个移动过程中，这条边，被走过的次数就是2 * m1。

简单的证明，如果树的点数n为偶数，一定能找到一条边，使得左部和右部的点数均为n/2，那么只要把左部和右部的点一一对应交换，那么这条边就一定被走过了2 * n/2次，和上面的结论符合

如果点数n为奇数（n>=3,n=1的情况不需要讨论嘛都不能交换），一定能找到一条边，左部的点数为n/2,右部点数为n/2+1，将左部的点和右部的n/2个点一一对应交换，那么这条边就一定能走过2 * n/2，至于右部还有1个点没有交换，只要将该点和此时右部中的一个点交换即可

所以问题转化为，枚举每条边，找出它左部和右部中点数的较小值m，这条被走过的次数就是2 m，产生的价值自然是2 m * w,再将左右边产生的价值累计即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100010
#define LL long long
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,head[N];
struct edge{
    int u,v,next;
    LL w;
    edge(){}
    edge(int __u,int __v,LL __w){
        u = __u; v = __v; w = __w;
    }
}e[2*N];
int cnt[N],back[N];
LL ANS;

inline void add(int u,int v,LL w){
    e[tot] = edge(u,v,w);
    e[tot].next = head[u]; head[u] = tot++;
}

void dfs1(int u,int fa){
    cnt[u] = 1;
    for(int k = head[u]; k != -1; k = e[k].next){
        int v = e[k].v;
        if(v == fa) continue;
        dfs1(v,u);
        cnt[u] += cnt[v];
    }
}

void dfs2(int u,int fa,LL w){
    if(fa != -1){
        back[u] = n - cnt[u];
        int tmp = min(back[u] , cnt[u]);
        ANS += w*tmp*2;
    }
    for(int k = head[u]; k != -1; k = e[k].next){
        int v = e[k].v;
        LL w = e[k].w;
        if(v == fa) continue;
        dfs2(v,u,w);
    }
}

int main(){
 //   freopen("case.txt","r",stdin);
    int T,cas = 0;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        tot = 0; cl(head,-1);
        for(int i = 1; i < n; i++){
            int u,v; LL w;
            scanf("%d%d%I64d",&u,&v,&w);
            add(u,v,w); add(v,u,w);
        }
        ANS = 0;
        dfs1(1,-1);
        dfs2(1,-1,0);

        //for(int i = 1; i <= n; i++)
        //    printf("%d : %d %d\n",i,cnt[i],back[i]);
        printf("Case #%d: %I64d\n",++cas,ANS);
    }
    return 0;
}