自动搬运

查看原文

来自洛谷，原作者为

	jiayixuan1205 现在是文化课选手了

搬运于2025-08-24 21:44:01，当前版本为作者最后更新于2024-08-08 17:47:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解：P2977 [USACO10JAN] Cow Telephones G

题意

给出一棵树，每个节点限定一个可通过的最大值 $k$，每条边最大可通过值为 $1$，叶子仅通过最短路连接，求最多多少对叶节点可同时连接。

算法

考虑贪心。

分析

最简单的贪心想法就是将可连接的最近的节点两两连接，但是如果涉及到跨子树的情况就不正确了，因此我们转变思路。 首先，容易想到，最优秀的情况是在每个子树中节点恰好两两配对且不超过父亲节点的最大承载量。那么，就可以分出下面两种情况：

• 子树内存在可以相连的节点就优先处理。
• 剩余跨子树的节点考虑通过最短可行路径连接。

分别处理即可。

代码展示

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6+10; 
int n,k;
int res[N],val[N];
/*
   res:标记该子树是否有剩余节点未连接   
   val:记录这颗子树对答案的贡献 
*/ 
int ans;
int tot,head[N*2];

struct edge{
	int nex,to;
}e[N*2];

inline void add(int x,int y)//建边 
{
	tot++;
	e[tot].nex=head[x];
	e[tot].to=y;
	head[x]=tot;
}

inline void dfs(int x,int fa)//遍历 
{
	for(int i=head[x];i;i=e[i].nex)
	{
		if(e[i].to!=fa) 
		{
			dfs(e[i].to,x);
			if(res[e[i].to]==1)//子树内有剩余边 
			{
				if(res[x]==1)
				{
					val[x]++;//可贡献值++ 
					res[x]=0;
				}
				else if(val[x]!=k) res[x]=1;//有剩余 
			}
		}
	}
	ans+=val[x];
}

int main()
{
	cin>>n>>k;
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
		res[x]++;
		res[y]++;
	}
	dfs(1,0);
	cout<<ans<<endl;
	return 0;
}