P4189 [CTSC2010]星际旅行

看到讨论中有费用流了，就直接上了。

然而，开始不会建图，建完图后发现图又出现了死循环，弄死过不去，回去看题解发现是模拟费用流，泪目了。

Solution

仔细想想我们建出来的*一样的图，可以发现除了中间有费用交叉以外没有其他费用，神似P5470 [NOI2019] 序列，然后我们在题目中发现这玩意儿是棵树，我们仔细分析每一个终点在 $0$ 号点的情况又可以得出类似于 CF453C的震荡操作，于是我们可以得到 $0$ 的答案：

• 对于每一条链，由于链两端的值均大于 $1$ 所以我们可以一直从 $x$ 出发走到 $y$ 再回到 $x$（两个值同时减1），故对 $x$ 的答案贡献就是：$min(val[x],val[y])$，由于根节点始终保证可以走回来，所以我们不妨优先走叶子节点，将叶子压榨干净之后，再回来压榨路径上的其他节点。

void dfs(int x, int father)
{
	for(int i = h[x]; ~i;i = ne[i])
	{
		int j = e[i];
		if(father == j) continue;
		dfs(j, x);
		int v = min(val[x], val[j]);
		val[x] -= v;
		val[j] -= v;
		cnt += v * 2;
		if(val[j]) son[x] = j; // 记录最后还可以从哪来的 
	}
}

暂时不管那个注释，我们接着思考如何由父节点推及其他儿子节点，不难发现如果最后是由这个儿子走到父节点的话我们完全可以不再震荡，故这个儿子可以完全继承父节点的权值，而如果父节点还有值，但儿子节点没有值了我们就可以从父亲再走到儿子，儿子就等于父节点权值 $+1$，而当父节点和子节点都没有值了，那就不能上传了，子节点权值等于父节点权值 $-1$。

那么就做完了。

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 50000 + 5;
int n;
int a[N];
int idx;
int e[N << 1], ne[N << 1], h[N];
void add(int x, int y)
{
	idx ++;
	e[idx] = y, ne[idx] = h[x], h[x] = idx;
}
int val[N], cnt;
int son[N];
void dfs(int x, int father)
{
	for(int i = h[x]; ~i;i = ne[i])
	{
		int j = e[i];
		if(father == j) continue;
		dfs(j, x);
		int v = min(val[x], val[j]);
		val[x] -= v;
		val[j] -= v;
		cnt += v * 2;
		if(val[j]) son[x] = j; // 记录最后还可以从哪来的 
	}
}
int ans[N];
void dfs1(int x, int father)
{
	ans[x] = cnt;
	for(int i = h[x]; ~i;i = ne[i])
	{
		int j = e[i], type;
		if(j == father) continue;
		if(val[x]) val[x] --, cnt ++, type = 1;
		else if(son[j]) val[son[j]] --, cnt ++, type = 2;
		else val[j] ++, cnt --, type = 3;
		dfs1(j, x);
		if(type == 1) val[x] ++, cnt --;
		if(type == 2) val[son[j]] ++, cnt --;
		if(type == 3) val[j] --, cnt ++;
	}
}
int main()
{
	memset(h, -1, sizeof(h));
	scanf("%d", &n);
	for(int i = 0;i < n;i ++) scanf("%d", &val[i]);
	for(int i = 1;i < n;i ++)
	{
		int o, u;
		scanf("%d%d", &o, &u);
		add(o, u);
		add(u, o);
		val[o] --, val[u] --, cnt += 2; // 特别注意1
	}
	dfs(0, -1), dfs1(0, -1);
	for(int i = 0;i < n;i ++) printf("%d\n", ans[i]);
	return 0;
}

注，特别注意1：必须要减，上方的贪心过后一定能保证清零。这里减的即为费用流的的贪心流量，如果不减，那就是个裸的贪心。