[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("%dn",ans[i]);
return 0;
}