自动搬运

查看原文

来自洛谷，原作者为

	Sakura_梦瑶 **

搬运于2025-08-24 21:57:30，当前版本为作者最后更新于2019-08-12 22:37:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里是给出所有题解所没有的细节证明

首先 思考一个问题:只有一条链的时候,你可以选择任意一个相邻点对使得ans+=2,h[x]--,h[y]--，求如何选择会使ans最大。 首先当点数<=4的时候不管怎么操作,操作到无操作可选的时候,ans永远相等。 以<=4为起点这样数学归纳一下会发现不论点数多少 结论都是成立。

回归本题。 答案肯定会遍历每条边,所以先把每个点减去度数,然后贡献给答案，当做已经遍历一次了。此时 就等于把上面的问题归类在一棵树上了，因为一棵树其实会被多条链剖开，运用上面的结论，现在把他们随意操作掉统计答案就是从起点回到起点的答案了。如此贪心操作的结果 你会发现剩余的h的分布甚至都完全相同.

起点回到起点的答案已经被统计,现在只要从这个答案出发,更新其他点的答案即可。直接dfs,从父亲走向儿子。

第一个情况 倘若父亲的h>0 儿子的答案就是父亲的+1，父亲的h--然后向下继续更新。

第二个情况 父亲的h==0, 那么考虑 将原本的一次点对操作退回去让父亲和儿子的h同时++。儿子的答案就是父亲的答案-1.

第三个情况 父亲的h虽然==0 但是 儿子存在h>0的儿子 此时可以退父亲和儿子的流 然后让儿子的儿子之前跑来回 总的ans是++ 然后只有儿子的儿子的h--

至于向下更新的正确性 感性理解大致如下： 现在不存在任何一个相邻点对x,y 中x y的h>0 所以此时你不论去哪里 因为每条边一定会折返，所以一定会退流一次往返， 也就是说如果打算再从一个点x 遍历其他地方尝试让ans++ 是不可能的； 所以当前唯一的选择就是通过退流使得从x to y 合法。

综上所述所以第一步操作相对初始形态图是最优，第二步统计相对第一步操作完后的图是最优。通过结论套结论 可证如此是最优

#include<bits/stdc++.h>
#define N 1<<20
using namespace std;
int las[N],to[N],nxt[N],n,val[N],now,ans[N],p[N];
void dfs(int x,int f){
	for(int i=las[x];i;i=nxt[i])if(to[i]!=f)dfs(to[i],x);
	int c=min(val[f],val[x]);now+=c*2,val[x]-=c,val[f]-=c,val[x]?p[f]=x:0;
}
void dfs1(int x,int f){
	ans[x]=now;for(int i=las[x];i;i=nxt[i])if(to[i]!=f)
	 if(val[x])now++,val[x]--,dfs1(to[i],x),now--,val[x]++;
	 else if(p[to[i]])val[p[to[i]]]--,now++,dfs1(to[i],x),val[p[to[i]]]++,now--;
	 else val[to[i]]++,now--,dfs1(to[i],x),val[p[to[i]]]--,now++;
}
int main(){
	cin>>n;for(int i=1;i<=n;i++)scanf("%d",&val[i]);
	for(int i=1;i<n*2-1;i+=2)scanf("%d%d",&to[i],&to[i+1]),
	 to[i]++,to[i+1]++,now+=2,val[to[i]]--,val[to[i+1]]--,
	nxt[i]=las[to[i+1]],las[to[i+1]]=i,nxt[i+1]=las[to[i]],las[to[i]]=i+1;
	dfs(1,0),dfs1(1,0);for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
}