hdu2196 Computer(树形dp)

题意

找每个顶点，到树的某一端的最长距离

思路来源

https://www.cnblogs.com/dilthey/p/7186556.html

https://blog.****.net/u011815404/article/details/82960087

心得

dfs还真是神奇

树上dp真好玩

也就是一个先叶后根，一个先根后叶嘛

由于一个分支顶点最多连有父亲、左右子树

所以最多在三个方向上被更新，0记子树最长路，1记另一路最长路，2记父亲最长路

画一个有父亲和左右子树的分支节点

分情况讨论那个左子树是不是最长路节点就ok了

代码

#include <iostream>
#include <algorithm> 
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const int INF=0x3f3f3f3f;
const int maxn=1e4+10;
const int mod=1e9+7;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<int,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std; 
struct edge
{
	int to,nex,w;
}e[maxn]; 
int head[maxn],cnt,n; 
int dp[maxn][3];
//dp[u][0]代表某一子树最长(最长) 
//dp[u][1]代表另一子树最长(次长) 
//dp[u][2]代表父亲最长
void add(int u,int v,int w)
{
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].nex=head[u];
	head[u]=cnt++;
} 
void init()
{
	mem(head,-1);
	cnt=0;
	mem(dp,0);
}
void dfs1(int now,int fa)//叶->根回溯 
{
	for(int u=head[now];~u;u=e[u].nex)
	{
		int v=e[u].to,w=e[u].w;
		dfs1(v,now);
		int temp=dp[v][0]+w;
		if(temp>=dp[now][0])
		{
			dp[now][1]=dp[now][0];//次短
			dp[now][0]=temp; 
		}
		else if(temp>dp[now][1])
		{
			dp[now][1]=temp;
		}
	}
}
void dfs2(int now,int fa)//根->叶下溯 
{
	for(int u=head[now];~u;u=e[u].nex)
	{
		int w=e[u].w,v=e[u].to;
		if(dp[now][0]==dp[v][0]+w)//now为父 u路为now的最长路子树 
		{
			dp[v][2]=max(dp[now][2],dp[now][1])+w;
			//另一路和父亲的最大值+w 
		}
		else//now为父 u路为now的次长路子树 即另一路更长 
		{
			dp[v][2]=max(dp[now][2],dp[now][0])+w; 
		} 
		dfs2(v,now);
	}
}
int main()
{ 
   while(~scanf("%d",&n)&&n)
   {
   init();
   for(int i=2;i<=n;++i)
   {
   	int v,w;
   	scanf("%d%d",&v,&w);
   	add(v,i,w);//有根树 
   }
   dfs1(1,-1);//找儿子 叶->根 
   dfs2(1,-1);//找父亲 根->叶
   for(int i=1;i<=n;++i)
   printf("%d\n",max(dp[i][0],dp[i][2]));
   }
   return 0;
}