sgu 149 Computer Network

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

【重做DP系列】树DP

题意:给出一棵无根树(可当做根为1处理,因为数据的格式决定了),节点从1到n标号,输出每个节点到其余节点的最远距离。数据给出方式方便了一些处理,第k行就是给出了k的父亲和其指向父亲的那条边的权。另外权无负数

思考:以1定根后,要知道1个节点到其余节点的最远距离,只有两种可能,一种是到其子树下的某个节点,一个是沿祖先返回再去到某些节点。在其子树下的一些信息,比较容易确定,下面定义几个值并说明它的意义

maxval[rt][0],maxval[rt][1],表示以rt为根的子树,到子树下的节点最远距离和次远距离,但是这里要注意一个细节

最远距离的节点,次远距离的节点一定在不同分支内,所以准确的定义,看下面解释(网上很多解题说得不够准确虽然是这个意思)

好像1有3个儿子,2,3,4,那么说1下面有3个分支,1到2分支的最远距离是1,到3分支的最远距离是5,到4分支的最远距离是10,那么maxval[1][0] = 1; maxval[1][1] = 5;注意这个5,是相对于分支而言,是次远值,对整个子树而言不一定是;打比方,1到2分支的最远距离是1,次元距离可能是2,这个2比5还小,但是我们不能记录2,要记录5,这就是maxval的准确意义,是相对应分支而言的

另外设置一个index[rt][0],index[rt][1]对应记录maxval值是来自于那个分支的

sample: maxval[1][0] = 1; index[1][0] = 2; maxval[1][1] = 5; index[1][1] = 3;

接着考虑往上走的情况,先来考虑一下暴力的情况,从节点u出发,走到其父亲fa,有2种走法,一个是继续向上走,一个是从fa那些下面;如果是从fa那里下面,那当然是下去最远距离的分支;但是如果u就在fa的最远分支里,那是不能走的,那就走向次远分支(这就是为什么要顺便记录下次远的原因);如果是从fa往上走,走到了fa的父亲ffa,同样也是这样做,知道走到根1那里。

这时候如果考虑u的儿子uu怎么往上走,会发现,做了重复的工作,uu走向u,再走向fa,再走向ffa,这个路径和之前u走过的是一样的,所以,这就产生了一个递推的性质,如果我们从某个节点u开始,计算出向上走的最大值,那么它的儿子uu可以不必再走一次,而是利用它父亲向上走的最大值

up[rt]表示节点rt向上走能走出的最远距离

设u是rt的儿子,那么u可以走向rt,然后就向下走了(那就当然是走向另外一个分支),看看u是否在rt的最远分支内,不在的话就走向rt的最远分支,在的话就走向次远分支;u可以走向rt,然后继续向上走,从此以后,就是rt以前做过的事情,不用做了,直接利用up[rt]

up[u] = dir[u] + max(up[rt] , maxval) (dir[u]表示u到其父亲的边权)

(无论如何都向上走了一步,记得加上dir[u],maxval的值要么是最远或次远看所在分支)

那么对于一个节点的最远距离,那么就是 max(maxval[rt][0] , up[rt]) (要么下走要么上走)

注意:这题说难不算太难,但是需要两次dfs,一次构造出maxval的值,一次构造出up的值,maxval的值是通过儿子去更新父亲的,up的值是利用父亲的值去更新的,刚好方向相反,因而这题的思想还是比较经典的

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 10010
#define INF 0x3f3f3f3f
#define cl memset
#define pb push_back
#define mp make_pair
#define pii pair<int,int>

int n;
int maxval[N][2],index[N][2],up[N],dp[N];
int fa[N],dir[N];
vector<pii>t[N];

void dfs(int u){
maxval[u][0] = maxval[u][1] = 0;
index[u][0] = index[u][1] = -1;
for(int i = 0; i < t[u].size(); i++){
int v = t[u][i].first;
dfs(v);
if(maxval[v][0] + dir[v] > maxval[u][0]){
maxval[u][1] = maxval[u][0];
index[u][1] = index[u][0];
maxval[u][0] = maxval[v][0] + dir[v];
index[u][0] = v;
}
else if(maxval[v][0] + dir[v] > maxval[u][1]){
maxval[u][1] = maxval[v][0] + dir[v];
index[u][1] = v;
}
}
}

void DFS(int u){
int temp;
if(index[fa[u]][0] != u)
temp = maxval[fa[u]][0];
else
temp = maxval[fa[u]][1];
up[u] = dir[u] + max(up[fa[u]] , temp);
dp[u] = max(maxval[u][0] , up[u]);
for(int i = 0; i < t[u].size(); i++){
int v = t[u][i].first;
DFS(v);
}
}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 1; i <= n; i++)
t[i].clear();
for(int u = 2; u <= n ; u++){
int par,w;
scanf("%d%d",&par,&w);
dir[u] = w; fa[u] = par;
t[par].pb(mp(u,w));
}
dfs(1);

dp[1] = maxval[1][0]; up[1] = 0;
for(int i = 0; i < t[1].size(); i++){
int v = t[1][i].first;
if(index[1][0] != v)
up[v] = dir[v] + maxval[1][0];
else
up[v] = dir[v] + maxval[1][1];
dp[v] = max(maxval[v][0] , up[v]);

for(int k = 0; k < t[v].size(); k++)
DFS(t[v][k].first);
}
/*
puts("----------------");
for(int i = 1; i <= n; i++)
printf("%d : %d[%d] %d[%d] %d\n",i,maxval[i][0],index[i][0],
maxval[i][1],index[i][1],up[i]);
puts("----------------");
*/
for(int i = 1; i <= n; i++)
printf("%d\n",dp[i]);
//cout << endl;
}
return 0;
}