HDU2196 树状DP

树形DP题，做的有些艰难，以前没怎么做过这方面的题目，有些理不清楚，题意很简单，就是给你一些电脑，每两台电脑之间若要连通是需要一定的权值的，把这些电脑按照input连在一起，形成一颗树，问树中每一个节点 到另一个节点（不确定是哪个几点）的距离值中最大距离，

我们知道每一个节点最大值无非来自两个地方，1：来自于他的子树中2；从他父亲节点过来的，但是有个地方要注意，从父节点过来的有可能是直接的，也有可能是父亲的最大距离加上他与父亲的距离，意思就是次长距离加上他与父亲的距离，所以需要两边DFS，第一次从他子树中寻找出最大距离跟次大距离，然后第二次DFS直接对父亲过来的进行更新即可

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-7

#define inf 0xfffffff
const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;
//

const int N = 10000 + 5;

int n;
int cnt;
int head[N];//头节点
int maxn[N];//该节点下面子树最大距离
int smaxn[N];//该节点下面子树次大距离
int maxid[N];//最大距离所对应的ID
int smaxid[N];//次大距离所对应的ID

struct Node {
	int to;
	int nex;
	int w;
}edge[N*2];

void clear() {
	cnt= 0;
	memset(head,-1,sizeof(head));
}

void addedge(int u,int v,int w) {
	edge[cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].nex=head[u];
	head[u]=cnt++;
}
//求节点V子树的最大距离，p是v的父亲节点
void dfs1(int u,int p) {
	maxn[u] = 0;
	smaxn[u] = 0;
	for(int i=head[u];i!=-1;i=edge[i].nex) {
		int v=edge[i].to;
		if(v == p)continue;
		dfs1(v,u);
		if(smaxn[u] < maxn[v] + edge[i].w) {
			smaxn[u] = maxn[v] + edge[i].w;
			smaxid[u] = v;
			if(smaxn[u] > maxn[u]) {
				swap(smaxn[u],maxn[u]);
				swap(smaxid[u],maxid[u]);
			}
		}
	}
}
//p是u的父亲节点，
void dfs2(int u,int p) {
	for(int i=head[u];i!=-1;i=edge[i].nex) {
		int v=edge[i].to;
		if(v == p)continue;
		if(v == maxid[u]) {
			if(edge[i].w + smaxn[u] > smaxn[v]) {
				smaxn[v] = edge[i].w + smaxn[u];
				smaxid[v] = u;
				if(smaxn[v] > maxn[v]) {
					swap(smaxn[v],maxn[v]);
					swap(smaxid[v],maxid[v]);
				}
			}
		}
		else {
			if(edge[i].w + maxn[u] > smaxn[v]) {
				smaxn[v] = edge[i].w + maxn[u];
				smaxid[v] = u;
				if(smaxn[v] > maxn[v]) {
					swap(smaxn[v],maxn[v]);
					swap(maxid[v],smaxid[v]);
				}
			}
		}
		dfs2(v,u);
	}
}

int main() {
	while(scanf("%d",&n)==1) {
		clear();
		int v,w;
		for(int i=2;i<=n;i++) {
			scanf("%d %d",&v,&w);
			addedge(i,v,w);
			addedge(v,i,w);
		}
		dfs1(1,-1);
		dfs2(1,-1);
		for(int i=1;i<=n;i++)
			printf("%d\n",maxn[i]);
	}
	return EXIT_SUCCESS;
}

HDU2196 树状DP

原文：http://blog.csdn.net/yitiaodacaidog/article/details/18323261