自动搬运

查看原文

来自洛谷，原作者为

	Thunder_S 咖啡馆与广场有三个街区，就像霓虹灯到月亮的距离。

搬运于2025-08-24 22:08:48，当前版本为作者最后更新于2021-10-05 11:23:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

不一样的阅读体验

Solution

可以证明，如果一条公交线路可以在子树内建成，就不会在往子树外走。

简单的证明：如果当前子树内有可以连的线路，如果往外走，要么与当前连边数一致，要么多连，答案不会更优。

因此考虑贪心。设 $a_i$ 和 $b_i$ 表示父亲要走过来多少和要往父亲走多少。

对于当前节点 $x$，它的子节点 $son$ 只有 $a_i$ 和 $b_i$ 中的一个可以传递到 $x$，那么另一个就可以记录答案。

另外，对于节点 $x$，优先让其在内部建线路，剩余的再传递上去。

Code

#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;
struct ndoe
{
	int to,next,head,fx;
}tree[N<<1];
int n,x,y,ans,tot,a[N],b[N];
void add(int x,int y,int opt)
{
	tree[++tot].to=y;
	tree[tot].fx=opt;
	tree[tot].next=tree[x].head;
	tree[x].head=tot;
}
void dfs(int x,int fa)
{
	for (int i=tree[x].head;i;i=tree[i].next)
	{
		int v=tree[i].to;
		if (v==fa) continue;
		dfs(v,x);
		if (tree[i].fx)//看能传递哪一部分，另外一部分计入答案
		{
			ans+=a[v];
			b[x]+=max(b[v],1);
		}
		else
		{
			ans+=b[v];
			a[x]+=max(a[v],1);
		}
	}
	int t=min(a[x],b[x]);
	a[x]-=t;b[x]-=t;ans+=t;//优先在内部连边
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		add(x+1,y+1,1);add(y+1,x+1,0);
	}
	dfs(1,0);
	printf("%d\n",ans+max(a[1],b[1]));
	return 0;
}