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