「Hdu 2196」Computer (树形DP(二次扫描换根) / 树的直径)

Hdu 2196
题意:给出一棵带边权树,求出每个点的到最远点的距离。

显然的一道无根树DP,所以先DP求一次最远点,然后再看怎么转移。
记$maxd(u)$为以$u$为根子树中的节点到根的最远点的距离。
这里有一种非常麻烦的情况就是父亲的题目所求答案的这条最长链就在这个分支中。那么我们只能选取一条其他分支的最大答案进行更新。
设$dp(u,0/1)$为以$u$为根到$u$点的最远点的距离。直接转移即可。

树直径做法:因为每个点到某个直径端点距离最远,所以求出直径端点再搜一次即可。

知识点
1、被自己举了反例的东西一定要记得完全错误再叉!

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 10000 + 5;
int n, maxd[MAXN], cid[MAXN], dp[MAXN][2]; // 0 最远,1 次远
vector<int > G[MAXN], val[MAXN];
void dfs1(int u, int fa) {
cid[u] = maxd[u] = 0;
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v != fa) {
dfs1(v, u);
if (maxd[v] + val[u][i] > maxd[u]) {
cid[u] = maxd[u];
maxd[u] = maxd[v] + val[u][i];
} else if (maxd[v] + val[u][i] > cid[u]) cid[u] = maxd[v] + val[u][i];
}
}
}
void dfs2(int u, int fa) {
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v != fa) {
if (val[u][i] + maxd[v] == dp[u][0]) { // 父亲最长距在本孩子
int gg[2];
gg[0] = dp[u][1] + val[u][i], gg[1] = maxd[v];
sort(gg, gg + 2);
dp[v][0] = gg[1], dp[v][1] = gg[0];
} else {
dp[v][0] = dp[u][0] + val[u][i], dp[v][1] = dp[u][1] + val[u][i]; // 不在一定是上面的u最优
}
dfs2(v, u);
}
}
}
void clean() {
ms(dp, 0);
for (LL i = 0; i <= n; ++i) G[i].clear(), val[i].clear();
}
int solve() {
clean();
for (int p, v, i = 2; i <= n; ++i) {
scanf("%d%d", &p, &v);
G[i].push_back(p), G[p].push_back(i);
val[i].push_back(v), val[p].push_back(v);
}
dfs1(1, 0);
dp[1][0] = maxd[1], dp[1][1] = cid[1], dfs2(1, 0);
for (int i = 1; i <= n; ++i) printf("%d\n", dp[i][0]);
return 0;
}
}
int main() {
while (scanf("%d", &flyinthesky::n) == 1) flyinthesky::solve();
return 0;
}
/*
9
1 5
2 4
3 1
1 6
5 1
5 2
5 1
7 3
*/

------ 本文结束 ------