526互联

Codeforces 1396E - Distance Matching

发布时间 2023-07-14 10:48:03作者: tzc_wk

先考虑一下合法的 \(k\) 的上界和下界是什么以及如何达到上界和下界，我们找出树的一个重心 \(R\) 并以 \(R\) 为根 dfs 一遍整棵树，那么：

  • 下界为 \(\sum(siz_i\bmod 2)\)，构造方法是从下往上钦定，对于一个点考虑其所有没有匹配的儿子，如果是偶数个就将它们两两匹配，如果是奇数个就将它们两两匹配，然后剩余的那个与当前节点匹配。
  • 上界为 \(\sum siz_i\)，方法就是将根节点每个子树看作一种颜色，然后每次从颜色数量最多的两种颜色里各取一个点匹配。

另外，\(k\) 的奇偶性必须与 \(L\) 和 \(R\) 相同，否则也无解。

剩余的情况是否都有解呢？考虑通过构造说明。考虑这样一种思路，我们先假设所有点都与一个颜色与其不同的点匹配（即 \(k\) 达到上界），然后每次我们选择下界对应的构造方案中的两个点 \(x,y\)，然后尝试将它们匹配，这样 \(k\) 会减去 \(dep_x+dep_y-\text{dis}(x,y)\)，如此下去直到 \(k\) 达到我们想要的值即可。更具体地，对于根节点的每个子树，我们记录下，在下界对应的构造方案中，该子树中的点的匹配情况，然后每次我们取出剩余节点数最多的颜色（目的是为了保证任意时刻剩余部分可以做到“两两匹配且每对匹配点颜色不同），然后取出里面最深的一对匹配点，如果它俩匹配后 \(k\) 的值比我们想要的小，那么我们设 \(u\) 为两点中较深的一者，我们考虑将 \(u\) 与其某个祖先匹配使得匹配后的 \(k\) 刚好是我们想要的值（由于调整后的 \(k\) 值关于另一个匹配点的深度形成的函数为斜率为 \(2\) 的等差数列，且我们的奇偶性是有保证的，所以一定能找到），否则就将它俩匹配。剩余的部分就用达到上界的构造方法即可。

const int MAXN=1e5;
const int INF=0x3f3f3f3f;
int n,hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec;ll k;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int mx0[MAXN+5],siz0[MAXN+5],rt;
void dfs0(int x,int f){
	siz0[x]=1;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f)continue;dfs0(y,x);
		siz0[x]+=siz0[y];chkmax(mx0[x],siz0[y]);
	}chkmax(mx0[x],n-siz0[x]);if(mx0[x]<mx0[rt])rt=x;
}
int dep[MAXN+5],siz[MAXN+5],cnt[MAXN+5],fa[MAXN+5];ll L,R;
void dfs1(int x,int f){
	siz[x]=1;fa[x]=f;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f)continue;
		dep[y]=dep[x]+1;dfs1(y,x);siz[x]+=siz[y];
	}
}
bool vis[MAXN+5],die[MAXN+5];
vector<pii>pr[MAXN+5],res;
vector<int>pt[MAXN+5]; 
void dfs2(int x,int f,int r){
	vector<int>vec;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f)continue;
		dfs2(y,x,r);if(!vis[y])vec.pb(y);
	}
	if(vec.size()%2)vec.pb(x),vis[x]=1;
	for(int i=0;i<vec.size();i+=2)pr[r].pb(mp(vec[i],vec[i+1]));
}
void dfs3(int x,int f,int r){
	if(!die[x])pt[r].pb(x);
	for(int e=hd[x];e;e=nxt[e])if(to[e]!=f)dfs3(to[e],x,r);
}
int main(){
	scanf("%d%lld",&n,&k);
	for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
	mx0[0]=INF;dfs0(1,0);dfs1(rt,0);
	for(int i=1;i<=n;i++)R+=dep[i],L+=siz[i]&1;
	if(k<L||k>R||k%2!=L%2)return puts("NO"),0;
	puts("YES");
	for(int e=hd[rt];e;e=nxt[e])dfs2(to[e],rt,to[e]);
	ll nd=R-k;set<pii>st;
	for(int e=hd[rt];e;e=nxt[e]){
		int x=to[e];reverse(pr[x].begin(),pr[x].end());
		st.insert(mp(cnt[x]=siz[x],x));
	}
	while(!st.empty()&&nd){
		pii p=*st.rbegin();st.erase(st.find(p));
		int x=p.se;pii pp=pr[x].back();pr[x].ppb();
		int u=pp.fi,v=pp.se;if(dep[u]>dep[v])swap(u,v);
		int dlt=dep[u]+dep[v]-((dep[u]==dep[v])?2:1);
		if(nd>=dlt)nd-=dlt,die[u]=die[v]=1,st.insert(mp(p.fi-2,x)),res.pb(mp(u,v));
		else{
			int k=dep[u]-nd/2,w=u;while(k--)w=fa[w];
			die[u]=die[w]=1;nd=0;st.insert(mp(p.fi-1-(w!=rt),x));
			res.pb(mp(u,w));
		}
	}
	for(int e=hd[rt];e;e=nxt[e])dfs3(to[e],rt,to[e]);
	while(!st.empty()){
		pii p=*st.rbegin();st.erase(st.find(p));
		if(!p.fi)break;
		if(p.fi==1&&(st.empty()||(st.rbegin()->fi)==0)){
			res.pb(mp(pt[p.se].back(),rt));break;
		}
		pii pp=*st.rbegin();st.erase(st.find(pp));
		res.pb(mp(pt[p.se].back(),pt[pp.se].back()));
		pt[p.se].ppb();pt[pp.se].ppb();
		st.insert(mp(p.fi-1,p.se));st.insert(mp(pp.fi-1,pp.se));
	}
	for(pii p:res)printf("%d %d\n",p.fi,p.se);
	return 0;
}
/*
6 4
1 2
2 3
2 4
1 5
5 6
*/