自动搬运

查看原文

来自洛谷，原作者为

	Mirach 诶这里还可以填东西？

搬运于2025-08-24 21:49:02，当前版本为作者最后更新于2018-03-28 20:53:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Thought

题目分析（直接看解法的请往下翻）：

这题一眼有点像最小路径覆盖（二分图or网络流），但实际上并不一样，因为全局最优与局部最优可能会有冲突

实际上观察这题的数据，推测复杂度$O(n)$

不难想到选取的$I$条路径都是从叶子到叶子存在最优解

那么发现貌似叶子节点中最多只有$I*2$个会被覆盖（每条路径从叶子到叶子，覆盖$2$个），类似的，发现从叶子节点往内推一层也是最多只有$I*2$个会被覆盖，那么大胆猜测，如果从叶子节点向内拓扑分层后每一层最多只有$I*2$个会被覆盖，考虑到每一层的节点并不一定有$I*2$个，所以每一层要考虑节点数的限制，最后将所有层加起来即可

这样做虽然没有直接考虑每一条路径，但由于路径之间是可相交的，所以可以保证每一层的点都可以满足覆盖 $min(I*2,tot)$ $tot$为当前层点数 个的要求

Solution

从叶子拓扑排序处理出节点的层，每一层对答案的贡献为$min(2*I,tot)$

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rg register
#define cl(x) memset(x,0,sizeof(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>0?(x):(-(x)))

template <typename _Tp> inline _Tp read(_Tp&x){
	rg char c11=getchar(),ob=0;x=0;
	while(c11^'-'&&!isdigit(c11))c11=getchar();if(c11=='-')c11=getchar(),ob=1;
	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();if(ob)x=-x;return x;
}

const int N=1005000;
struct Edge{int v,nxt;}a[N<<1];
int head[N],tot[N],deg[N],lay[N],vis[N];
int n,k,_(0);

inline void add(int u,int v){
	a[++_].v=v,a[_].nxt=head[u],head[u]=_;++deg[u];
	a[++_].v=u,a[_].nxt=head[v],head[v]=_;++deg[v];
}

void topology(){
	queue <int> q;
	for(rg int i=1;i<=n;++i)if(deg[i]==1)vis[i]=1,++tot[lay[i]=1],q.push(i);
	while(!q.empty()){
		rg int x=q.front();q.pop();
		for(rg int i=head[x];i;i=a[i].nxt)
			if(!vis[a[i].v])
			if((--deg[a[i].v])==1)
			vis[a[i].v]=1,++tot[lay[a[i].v]=lay[x]+1],q.push(a[i].v);
	}
	return ;
}

int main(){
	read(n);read(k);
	for(rg int i=1,x,y;i<n;++i)add(read(x),read(y));
	topology();
	rg int ans(0);
	for(rg int i=1;tot[i];++i)ans+=min(k<<1,tot[i]);
	printf("%d\n",ans);
	return 0;
}