noip模拟 *第一题（基础dp?）

我们令 \(dp_i\) 表示正常处理完 \(i\) 子树节点的最优步数
转移时我们分两种情况

• 该根节点的每个子节点之间没有联系
  直接将 \(dp\) 数组相加即可。
• 第二种情况就是有联系，该情况可以再分两种情况
  1. 存在一点的 \(dp\) 值小于从该节点向下找一遍再返回的步数，那么我们就可以根据这条主链来让其他 \(dp\) 值大于从该节点向下找一遍再返回的步数的子节点遍历一边该子节点再返回。
  2. 不存在，也就是说每个子节点的 \(dp\) 值均大于从该节点向下找一遍再返回，那么我们需要让其中一个点进行 \(dp\) 所代表的操作，显然应该找一个最小的 \(dp\) 值。

\(dp\) 代码：

inline void dfs(int now,int pre) {
	dep[now]=dep[pre]+1; size[now]=1;
	int a=0,b=INF;
	if(du[now]==1) { dp[now]=dep[now]-1; return; }
	for(re int i=head[now],to;~i;i=edge[i].nxt) {
		if((to=edge[i].var)==pre) continue;
		dfs(to,now);
		size[now]+=size[to];
		a+=min(dp[to],2*size[to]);  
		b=min(b,dp[to]-2*size[to]); 
	}
	dp[now]=a+max(b,0ll); //存在负数的话那肯定有一点的dp大于2×size,不用再加dp值
	// 否则就是 dp-2*size+2*size，相当与加上该点的dp值
}

noip模拟 *第一题（基础dp?）

原文：https://www.cnblogs.com/zjxlm/p/15164996.html