hdu 2196 Computer（树形dp）（暂存于CSDN，最终保存于牛客或洛谷）

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2196

解题思路

化无根树为有根树进行分析： 蓝色区域为以2为根的子树，红色区域为以2的父亲结点1为根的（子）树，不包含以2为根子树的部分。 我们定义： dp[i][0]表示节点i与以i为根的子树内最远的叶子节点之间的距离； dp[i][1]表示节点i与非子树内最远的叶子节点之间的距离。 disMAX[i]的含义与dp[i][0]一致； disMIN表示以i为根节点的子树内，节点i与次最远叶子节点之间的距离。

dp[i][0]比较好求，只要先dfs到底，在递归刷新每个节点的最大距离即可。 而求dp[i][1]则需要边dfs边刷新dp[i][1]。 假设节点u有n个子节点，分别是v1,v2…vn 那么 如果vi不是u最长距离经过的节点，dp[vi][1] = cost(vi,u)+max(disMAX[u], dp[u][1])； 如果vi是u最长距离经过的节点，那么不能选择f[u][0],因为这保存的就是最长距离，要选择以u为根子树的次最大距离，可得dp[vi][1] = cost(vi, u) + max(disMIN[u], dp[u][1])；

细节在代码中体现。

AC代码

#include
#define pb push_back
#define ll long long 
using namespace std;
const int N=1e5+100;
struct computer
{
	int to,cost;//to表示与i相连的节点，cost表示二者的边权
};
int n,to,cost;
ll dp[N][2],disMAX[N],disMIN[N],pathMAX[N];//dp，disMAX，disMIN含义如上，pathMAX[i]=j表示以i为根节点的最长路径的儿子节点为j。
vector g[N];
void dfs1(int x,int fa)//求disMAX（即dp[][0]），和disMIN，以及保存路径
{
	for(int i=0;idisMAX[x])//判断是否要刷新最大距离，刷新
		{
			disMIN[x]=disMAX[x];//把原最大距离给次最大距离
			disMAX[x]=dis;//更新最大距离
			dp[x][0]=disMAX[x];//disMAX与dp[][0]同步刷新
			pathMAX[x]=g[x][i].to;//保存最大距离路径
		} 
		else if(dis>disMIN[x]) disMIN[x]=dis;//不刷新最大距离，判断一下是否刷新次最大距离
	}
}
void dfs2(int x,int fa){//求dp[][1]
	for(int i=0;i>n)
	{
		//每次的初始化不可缺少
		memset(dp,0,sizeof dp);
		memset(disMAX,0,sizeof disMAX);
		memset(disMIN,0,sizeof disMIN);
		memset(pathMAX,0,sizeof pathMAX);
		for(int i=1;ito>>cost;
			tmp.to=to,tmp.cost=cost;
			g[i].pb(tmp);
			tmp.to=i;
			g[to].pb(tmp);
		}
		
		dfs1(1,-1);
		dfs2(1,-1);
		
		for(int i=1;i