HDU 2196树形DP(2个方向)

HDU 2196

【题目链接】HDU 2196

【题目类型】树形DP(2个方向)

&题意：

题意是求树中每个点到所有叶子节点的距离的最大值是多少。

&题解：

2次dfs，先把子树的最大距离求dp[i][0]和次大距离dp[i][1]求出来；之后再一次dfs把从父亲走的最大距离dp[i][2]求出来，最后max(dp[i][0],dp[i][2])就是答案了。感觉求次大距离那块处理的很好，值得学习一下。
这题有很多好的题解，复制了一份，原链接：http://blog.csdn.net/angon823/article/details/52261423
这题一直被称为树形dp的经典是有它的道理的，因为树dp就是把dp放到树上做了，一般是从上到下或从下到上（利用回溯）的移转状态。而这题很合适的需要两次dfs。
对于<u,v>（有向），
dp[u][0]表示在u的子树下u的最远距离是多少
dp[u][1]表示在u的子树下（和dp[u][0]不是同一孩子）u的次远距离是多少
dp[u][2]表示通过u的父亲能走的最远距离是多少
第一次从下到上，对于<u,v>（有向），状态转移显然是 dp[u][0] = dp[v][0]+w[i]；所以要先算出dp[v][0]才能知道dp[u][0]。故是从下往上。
第二次从上往下，其实就是再遍历一边图，把dp[v][2]算出来，显然：
dp[v][2] = max(dp[u][2]，dp[v][0]+w[i]==dp[u][0]?dp[u][1]:dp[u][0]) + w[i]；
要算dp[v][2]，要先算dp[u][0]，所以从上往下。
最后的答案就是 max（dp[u][0]，dp[u][2]）

【时间复杂度】(O(n))

&代码：

#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <set>
#include <queue>
#include <cstring>
#include <algorithm>
#define cle(a,v) memset(a,(v),sizeof(a))
#define ll long long
const int maxn = 10000 + 7;

struct Edge {
	int v, w, next;
} edge[maxn * 2];
int head[maxn], tot;
void addedge(int u, int v, int w) {
	edge[tot].v = v;
	edge[tot].w = w;
	edge[tot].next = head[u];
	head[u] = tot++;
}
int dp[maxn][3];

void dfs1(int ft) {
	for (int i = head[ft]; ~i; i = edge[i].next) {
		int v = edge[i].v;
		dfs1(v);
		int w = edge[i].w;
		int temp = dp[v][0] + w;
		if (temp >= dp[ft][0]) {
			dp[ft][1] = dp[ft][0];
			dp[ft][0] = temp;
		}
		else if (temp > dp[ft][1]) {
			dp[ft][1] = temp;
		}
	}
}

void dfs2(int fa) {
	for (int i = head[fa]; ~i; i = edge[i].next) {
		int v = edge[i].v;
		if (dp[fa][0] == dp[v][0] + edge[i].w) {
			dp[v][2] = std::max(dp[fa][2], dp[fa][1]) + edge[i].w;
		}
		else {
			dp[v][2] = std::max(dp[fa][2], dp[fa][0]) + edge[i].w;
		}
		dfs2(v);
	}
}

int main() {
	freopen("1.in", "r", stdin);
	int n;
	while (~scanf("%d", &n)) {
		cle(head, -1); tot = 0;
		for (int i = 2; i <= n; i++) {
			int v, w;
			scanf("%d%d", &v, &w);
			addedge(v, i, w);
		}
		cle(dp, 0);
		dfs1(1);
		dfs2(1);
		// for (int i = 1; i <= n; i++) {
		// 	printf("i=%d %d %d %d
", i, dp[i][0], dp[i][1], dp[i][2]);
		// }
		for (int i = 1; i <= n; i++) {
			printf("%d
", std::max(dp[i][0], dp[i][2]));
		}
	}
	return 0;
}