[CTSC2010]星际旅行

https://www.luogu.org/problemnew/show/P4189

题解

模拟费用流。

首先有一个非常好的条件，每个点的限制次数都大于等于这个点的度数。

然后我们可以从\(0\)开始\(dfs\)一遍这棵树。

然后如果一条边连接的两个点的\(h\)同时\(>0\)，那么就来回走。

然后我们考虑再去从\(0\)号节点往每个节点走。

如果此时\(u\)的\(h>0\)，那么直接走就可以了。

如果不是这样，那么我们为了从\(u\)走到\(v\)，必须将上一次\(uv\)折返的路程去掉，这样会使\(v\)的次数\(+1\)，这时如果\(v\)的一个儿子的次数不为\(0\)，那么还可以继续折返一次。

代码

#include<bits/stdc++.h>

#define N 50009

using namespace std;

typedef long long ll;

int head[N],tot,h[N],ans[N],now,p[N],n;

inline ll rd(){

	ll x=0;char c=getchar();bool f=0;

	while(!isdigit(c)){if(c=='-')f=1;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

	return f?-x:x;

}

struct edge{

	int n,to;

}e[N<<1];

inline void add(int u,int v){

	e[++tot].n=head[u];e[tot].to=v;head[u]=tot;

}

void dfs(int u,int fa){

	for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){

		int v=e[i].to;

		dfs(v,u);

		int x=min(h[u],h[v]);

		now+=x*2;

		h[u]-=x;h[v]-=x;

		if(h[v])p[u]=v;

	}

}

void dfs2(int u,int fa){

	ans[u]=now;

	for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){

		int v=e[i].to;

		if(h[u]){

			h[u]--;now++;

			dfs2(v,u);

			h[u]++;now--;

		}

		else if(p[v]){

			h[p[v]]--;now++;

			dfs2(v,u);

			h[p[v]]++;now--;

		}

		else{

		    h[v]++;now--;

			dfs2(v,u);

			h[p[v]]--;now++;

		}

	}

}

int main(){

	n=rd();int u,v;

	for(int i=1;i<=n;++i)h[i]=rd();

	for(int i=1;i<n;++i){

		u=rd()+1;v=rd()+1;

		add(u,v);add(v,u);

		h[u]--;h[v]--;now+=2;

	}

	dfs(1,0);

	dfs2(1,0);

	for(int i=1;i<=n;++i)printf("%d\n",ans[i]);

	return 0;

}