hdu 2196 コンピュータ#
木構造の DP、かなり難しい
問題#
重み付きの木が与えられた場合、各ノードから最も遠いノードまでの距離を求める。
入力:
-
nが 1 つ -
次の
n行には、各行に 2 つの整数j、wがあり、i行目は(i+1)からjまでの重みwの辺を表す。
なぜ入力をここに置いたのか、最初に間違えて見てしまったからです。。。
解法#
まず、1（または他のノード）をルートとして選ぶ。
ノードの最も遠い距離は、その子供たちまたは親から見つけることができる。
したがって、彼の「子供の中での最も遠い距離」と「彼の親の / 彼を通らない / 子供の中での最も遠い距離、彼の親から彼へのエッジの重みを加えたもの」の最大値を取るだけです。
2 回の DFS を行い、最初の DFS では各ノードの子供の最も遠い距離と、もう 1 つの子供を通る最も遠い距離（2 番目に遠い距離ではない）を求めます。
2 回目の 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;
}