HDU2196.Computer(树形DP）

HDU2196.Computer(树形DP）

题目传送门

思路：每个结点的最大距离转化为到子树结点的最大距离与到上部最大的距离的较大值。到上部最大距离要分两种情况（在最长距离子树上和不在最长距离子树上）通过两次DFS就可完成状态转移。具体看代码。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node{
	int id,d;
};
vector<node>e[N];
int dp[N][3],n; //dp[i][0],dp[i][1],dp[i][2] 分别表示结点i到子树最大距离,次大距离,和结点i到上部的最大距离 
void dfs1(int u){ //dfs1 求结点u到子树的最大距离和第二大距离(以便于分情况讨论) 
	int d1=0,d2=0;
	for(auto v:e[u]){
		 dfs1(v.id);
		 int tmp=dp[v.id][0]+v.d;
		 if(tmp>=d1){ //更新最大距离和次大距离 
		 	d2=d1,d1=tmp;
		 }
		 else if(tmp<d1&&tmp>d2) d2=tmp;//更新次大距离 
	}
	dp[u][0]=d1,dp[u][1]=d2;
}
void dfs2(int u){
	for(auto v:e[u]){
		if(dp[v.id][0]+v.d==dp[u][0]) //若子结点在u的最长子树上.则要用次大距离来更新 
			dp[v.id][2]=max(dp[u][2],dp[u][1])+v.d;
		else dp[v.id][2]=max(dp[u][2],dp[u][0])+v.d;//否则用最长子树更新. 
		dfs2(v.id);
	} 
} 
int main(){
	while(~scanf("%d",&n)){
		for(int i=1;i<=n;i++) e[i].clear();
		memset(dp,0,sizeof dp);
		for(int i=2,x,y;i<=n;i++){
			scanf("%d%d",&x,&y);
			e[x].push_back({i,y});
		}
		dfs1(1);
		dfs2(1);
		for(int i=1;i<=n;i++)
			printf("%d\n",max(dp[i][0],dp[i][2]));
	}
	return 0;
}