Sgu/149

经典问题 简单的树形dp

//by hza
#include<cstdio>
 
const int MAX=10000+20;
int n;
int fa[MAX],ca[MAX],t[MAX],c[MAX],begin[MAX],next[MAX],top;
int dist[MAX],deep1[MAX],deep2[MAX],level[MAX];
 
void addedge(int x,int y,int v)
{
	t[++top]=y;c[top]=v;
	next[top]=begin[x];begin[x]=top;
	fa[y]=x;ca[y]=v;
}
 
void init()
{
	int y,x,v;
	scanf("%d",&n);
	for(y=2;y<=n;++y)
	{
		scanf("%d%d",&x,&v);
		addedge(x,y,v);
	}
}
 
void dfs(int u)
{
	int i,v;
	deep1[u]=deep2[u]=0;
	level[u]=level[fa[u]]+1;
	for(i=begin[u];i;i=next[i])
	{
		v=t[i];
		dfs(v);
		if(deep1[v]+c[i]>deep1[u])
		{
			deep2[u]=deep1[u];
			deep1[u]=deep1[v]+c[i];
		}else if(deep1[v]+c[i]>deep2[u])
			deep2[u]=deep1[v]+c[i];
	}
}
 
void solve(int u)
{
	int i,v;
 
	dist[u]=dist[fa[u]];
	if( deep1[u]+ca[u]==deep1[fa[u]] )
	{
		if(deep2[fa[u]]>dist[u])dist[u]=deep2[fa[u]];
	}else
		if(deep1[fa[u]]>dist[u])dist[u]=deep1[fa[u]];
	dist[u]+=ca[u];
 
	for(i=begin[u];i;i=next[i])
	{
		v=t[i];
		solve(v);
	}
}
 
void work()
{
	dfs(1);
	solve(1);
	int i;
	for(i=1;i<=n;++i)
	{
		if(deep1[i]>dist[i])
			printf("%d\n",deep1[i]);
		else printf("%d\n",dist[i]);
	}
}
 
int main()
{
	init();
	work();
}

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
 
const int size = 11111;
 
int n, cnt, st[size], d[size], p[size];
 
struct Node {
	int v, w, next;
}edge[11111];
 
void addEdge(int u, int v, int w) {
	edge[cnt].v = v;
	edge[cnt].w = w;
	edge[cnt].next = st[u];
	st[u] = cnt++;
}
 
void dfs1(int u) {
	d[u] = 0;
	for (int i = st[u]; i != -1; i = edge[i].next) {
		int v = edge[i].v, w = edge[i].w;
		dfs1(v);
		d[u] = max(d[u], d[v]+w);
	}
}
 
void dfs2(int u) {
	int ma1 = 0, ma2 = 0, id;
	for (int i = st[u]; i != -1; i = edge[i].next) {
		int v = edge[i].v, w = edge[i].w;
		if (d[v] + w >= ma1) {
			if (ma1) ma2 = ma1;
			ma1 = d[v] + w; id = v;
		}
		if (d[v] + w >= ma2 && v != id)
			ma2 = d[v] + w;
	}
	for (int i = st[u]; i != -1; i = edge[i].next) {
		int v = edge[i].v, w = edge[i].w;
		if (v != id) p[v] = w + max(ma1, p[u]);
		else p[v] = w + max(ma2, p[u]);
		dfs2(v);
	}
}
 
int main() {
	cnt = 0;
	scanf("%d", &n);
	memset(st, -1, sizeof(st));
	int to, w;
	for (int i = 2; i <= n; i++) {
		scanf("%d %d", &to, &w);
		addEdge(to, i, w);
	}
	dfs1(1); dfs2(1);
	for (int i = 1; i <= n; i++)
		printf("%d\n", max(d[i], p[i]));
	return 0;
}