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;
}