hdu 2196 電腦#
樹形 dp，贼鸡儿难
題目#
給你一棵有邊權的樹，求每個點到離它最遠的點的距離
輸入：
? 一個n
? 接下來n行每行兩個整數j,w，其中第i行表示從(i+1)到j有一條權值為w的邊
為什麼我要把輸入放在這裡，因為我最開始看錯了。。。
解法#
首先把1（或者其他點）作為根。
一個節點的最遠距離就可以從它的兒子裡面或者父親裡面找
所以只要取他 “兒子裡的最遠距離” 和 “他父親的 / 不經過他的 / 兒子裡的最遠距離，加上他父親到他的邊權” 中的最大值
兩遍dfs，第一遍求每個節點兒子裡的最遠距離，和經過另外一個兒子的最遠距離（不是第二遠距離）。
第二遍判斷一下能走哪邊，然後取max
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;//能走父親最長的兒子
}
代碼#
#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;//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;
}