自动搬运

查看原文

来自洛谷，原作者为

	bellmanford 【没有谁会是失败者】

搬运于2025-08-24 21:31:56，当前版本为作者最后更新于2020-01-10 21:30:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

因为奇怪的名字和奇怪的背景才来写的。。。

话说这和差分有什么关系吗。。。

由于对于每个节点$u$都要求满足$cafe_u==table_u$

假设该节点的除叶子节点以外的所以儿子都已知其最多能放多少个女仆咖啡厅

由于已经满足$cafe_u==table_u$的关系，并不会对节点$u$的答案有什么影响

所以直接加就行了

对于剩下的节点$($也就是叶子节点和节点$u$本身$)$，根据贪心的思路，尽可能对半分

所以答案再加上剩下节点总数除以二的值

#include<iostream>
#include<cstdio>
using namespace std;

const int M=1e5+5;

int n,tot=0,in[M],ans[M],first[M];
struct Egde{
	int nxt,to;
}e[M<<1];

int read(){
	int x=0,y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') y=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*y;
}

void add(int x,int y){
	tot++;
	e[tot].nxt=first[x];
	first[x]=tot;
	e[tot].to=y;
}

void dfs(int u,int fa){
	int sum=1;//记录剩余节点个数 
	for(int i=first[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
		if(in[v]==1) sum++;
		else ans[u]+=ans[v];
	}
	ans[u]+=sum/2;
}

int main(){
	n=read();
	for(int i=1;i<=n-1;i++){
		int x=read(),y=read();
		add(x,y),add(y,x);
		in[x]++,in[y]++;//利用入度来判断是否为叶子节点 
	}
	dfs(1,0);
	printf("%d\n",ans[1]);
}