poj 1935 Journey

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

树dp

定1为根

black[u] = true,表示这个点要去到

mark[u] = true,表示点u及其子树中有点为黑色

dp[u]表示访问完u所在的子树的所有黑点,并且回到u的最小花费

要求的就是dp[1]吗?不是的,因为最后不需要回来!

其实只要1下面有m分支的话,可以知道,m-1个分支都是要全部走完再回到1的

但是有1个分支例外,准确来说是这个分支内的一条路径例外

实际上,只有一条路径不需要走回去,为了减少花费,我们要这条路径尽量大,不要走它,那就减去尽量多的花费

所以用一个Max[u],表示点u到它子树下面的黑点(不是叶子)的最远距离,那么对于1来讲就是Max[1]

答案就是dp[1] - Max[1]

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 50010
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,S,K,head[N];
struct edge{
int u,v,w,next;
edge(){}
edge(int __u,int __v,int __w){
u = __u; v = __v; w = __w;
}
}e[2*N];
bool black[N],mark[N];
int dp[N],Max[N];

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

void dfs1(int u,int fa){
if(black[u]) mark[u] = true;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
int w = e[k].w;
if(v == fa) continue;
dfs1(v,u);
if(mark[v]){
mark[u] = true;
dp[u] += (dp[v] + 2 * w);
Max[u] = max(Max[u],Max[v]+w);
}
}
}

int main(){
while(scanf("%d%d",&n,&S)!=EOF){
cl(head,-1); tot = 0;
for(int i = 1; i < n; i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w);
}
cl(black,false); cl(mark,false);
cl(dp,0); cl(Max,0);
scanf("%d",&K);
for(int i = 0; i < K; i++){
int x;
scanf("%d",&x);
black[x] = true;
}
dfs1(S,-1);
printf("%d\n",dp[S]-Max[S]);
}
return 0;
}