hdu 2196 Computer
树形dp，贼鸡儿难
题目
传送门
给你一棵有边权的树，求每个点到离它最远的点的距离
输入：
? 一个n
? 接下来n行每行两个整数j,w，其中第i行表示从(i+1)到j有一条权值为w的边
为什么我要把输入放在这里，因为我最开始看错了。。。
解法
首先把1（或者其他点）作为根。
一个节点的最远距离就可以从它的儿子里面或者父亲里面找
所以只要取他“儿子里的最远距离”和“他父亲的/不经过他的/儿子里的最远距离，加上他父亲到他的边权”中的最大值
两遍dfs，第一遍求每个节点儿子理的最远距离，和经过另外一个儿子的最远距离（不是第二远距离）。
第二遍判断一下能走哪边，然后取max
1
2
3
4
5
6
| if (path[p] == y) {
f[y][2] = max(f[p][2], f[p][1]) + e[i].w;
}
else {
f[y][2] = max(f[p][2], f[p][0]) + e[i].w;
}
|
Code
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
| #include <cstdio>
#define max(a, b) ((a) > (b) ? (a) : (b))
const int MAXN = 1e4 + 5;
struct ed {
int to, nex, w;
ed (void) {
to = nex = w = 0;
}
} e[MAXN << 1];
int head[MAXN], f[MAXN][3], path[MAXN];
int newp, n;
void insert (int p1, int p2, int w) {
++newp;
e[newp].w = w;
e[newp].to = p2;
e[newp].nex = head[p1];
head[p1] = newp;
}
void dfs1 (int p, int fa) {
for (int i = head[p]; i; i = e[i].nex) {
int y = e[i].to;
if (y != fa) {
dfs1(y, p);
if (f[p][0] < f[y][0] + e[i].w) {
f[p][1] = f[p][0];
f[p][0] = f[y][0] + e[i].w;
path[p] = y;
}
else if (f[p][1] < f[y][0] + e[i].w) {
f[p][1] = f[y][0] + e[i].w;
}
}
}
}
void dfs2 (int p, int fa) {
for (int i = head[p]; i; i = e[i].nex) {
int y = e[i].to;
if (y != fa) {
if (path[p] == y) {
f[y][2] = max(f[p][2], f[p][1]) + e[i].w;
}
else {
f[y][2] = max(f[p][2], f[p][0]) + e[i].w;
}
}
}
int main (void) {
while (scanf("%d", &n) != EOF) {
newp = 0;
for (int i = 1; i <= (n << 1); ++i) {
e[i] = ed();
}
for (int i = 1; i <= n; ++i) {
head[i] = 0;
path[i] = 0;
f[i][0] = f[i][1] = f[i][2] = 0;
}
for (int i = 2; i <= n; ++i) {
int p2, w;
scanf("%d%d", &p2, &w);
insert(i, p2, w);
insert(p2, i, w);
}
dfs1(1, 0);
dfs2(1, 0);
for (int i = 1; i <= n; ++i) {
printf("%d\n", max(f[i][0], f[i][2]));
}
}
return 0;
}
|
