自动搬运

查看原文

来自洛谷，原作者为

	TheLostWeak **

搬运于2025-08-24 22:38:11，当前版本为作者最后更新于2022-05-15 21:44:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一个 $O(n+m)$ 的解法？

称一条路径的 目标深度 为要满足分配给它的点对的限制至少需要达到的深度。

对于已经完成目标的路径，将直的路径（即一个端点是另一个端点的祖先的路径）称作 尚未匹配的路径，两条拼接在一起的直的路径称作 完成匹配的路径对。

考虑一个点子树内的信息，可以表示成若干个完成匹配的路径对、若干条尚未匹配的路径、若干条尚未完成目标的路径。

其中，对于尚未匹配的路径，我们能匹配就先匹配掉，因为已经完成的匹配之后可以拆，而现在没有匹配以后就不知道能不能匹配了。

如果有多条尚未完成目标的路径，我们只需保留一条路径继续做匹配，剩余的路径完成当前的任务就可以收工了。而保留的那条路径一定是 目标深度最小 的路径，所以对于其余尚未完成目标的路径可以直接在对应深度打标记表示到了那时会多出一条完成任务的 尚未匹配的路径。

先是对于边界情况，注意到几个结论：

• 对所有存在限制 $(x,y)$ 且子树内没有其他限制的点 $y$，肯定存在一种最优方案，使得所有 $y$ 都是某条路径的端点。（比较显然）
• 如果存在限制 $(x,y)$，且点 $y$ 子树内有其他限制，那么从子树内引一条路径上来一定不劣：
  • 如果子树内存在没有匹配的路径，显然引上来一定不劣。
  • 否则，新建路径只能得到一条向上的路径，拆散一对匹配并引一条路径上来 除了这条向上的路径外还能产生一条尚未匹配的路径。两者所需路径数相同，而后者显然更优一些。

然后再去考虑两个子树 $X,Y$ 信息的贪心合并：

• 如果都有尚未完成目标的路径，只要按照前面提到的方式保留一条即可。
• 假设 $Y$ 尚未匹配的路径较多，如果 $X$ 总路径数大于等于 $Y$ 的尚未匹配路径数，则除了路径总数为奇数时会多出一条路径之外，其余路径都能完成匹配；否则，就用 $X$ 所有路径去与 $Y$ 尚未匹配的路径匹配。

于是就做完了？时间复杂度 $O(n+m)$，代码也很好写。

不知道上面的过程会不会有什么问题，万一把我叉掉了通知我一下......

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 200000
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
using namespace std;
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
	int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
	I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
	Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
int n,m,ee,lnk[N+5];struct edge {int to,nxt;}e[N<<1];
int D[N+5];void dfs(CI x,CI lst=0)//预处理深度
{
	for(RI i=lnk[x];i;i=e[i].nxt) e[i].to^lst&&(D[e[i].to]=D[x]+1,dfs(e[i].to,x),0);
}
int a[N+5],b[N+5],mn[N+5],g[N+5],h[N+5];void Solve(CI x,CI lst=0)
{
	for(RI i=lnk[x],y;i;i=e[i].nxt) if((y=e[i].to)^lst)
	{
		if(Solve(y,x),b[y]+=h[D[x]],h[D[x]]=0,!a[y]&&!b[y]&&!mn[y]) continue;//子树为空，无需合并
		mn[y]==D[x]&&(++b[y],mn[y]=0);//完成了目标
		if(mn[x]&&mn[y]) mn[x]<mn[y]?++h[mn[y]]:(++h[mn[x]],mn[x]=mn[y]);else mn[x]|=mn[y];//合并尚未完成目标的路径
		if(b[x]>b[y]) swap(a[x],a[y]),swap(b[x],b[y]);//让y尚未匹配的路径数较大
		if(2*a[x]+b[x]>=b[y]) a[x]=a[x]+a[y]+(b[x]+b[y]>>1),b[x]=(b[x]+b[y])&1;//能匹配完
		else b[y]-=2*a[x]+b[x],a[x]=2*a[x]+b[x]+a[y],b[x]=b[y];//匹配不完
	}
	if(g[x]) mn[x]?mn[x]=min(mn[x],g[x]):(mn[x]=g[x],b[x]?--b[x]:a[x]&&(--a[x],++b[x]));//处理当前点上的要求
}
int main()
{
	RI Tt,i,x,y;read(Tt);W(Tt--)
	{
		for(read(n,m),ee=0,i=1;i<=n;++i) lnk[i]=a[i]=b[i]=g[i]=mn[i]=0;
		for(i=1;i^n;++i) read(x,y),add(x,y),add(y,x);D[1]=1,dfs(1);
		for(i=1;i<=m;++i) read(x,y),g[y]=g[y]?min(g[y],D[x]):D[x];//在y处记录要求
		Solve(1),writeln(a[1]+b[1]);
	}return clear(),0;
}