题意：
给一棵 \(n\) 个点的树，保证 \(n\) 为偶数，你需要将这 \(n\) 个点两两配对，使得每对点的距离和恰好为 \(k\)。判断无解或输出方案。
\(n\leq 10^5,k\leq n^2\)。
题解：
首先考虑 \(k\) 的上下界，这是一个很经典的问题，可以考虑每条边 \((u,v)\) 的贡献：假设左右两边子树大小分别为 \(sz_u,sz_v\)，那么该边贡献下界为 \(sz_u\bmod 2\)，上界为 \(\min(sz_u,sz_v)\)。于是 \(k\) 的上下界即为所有边的总和，记为 \([k_L,k_R]\)。
证明上下界是确界可以用调整法：若一条边被至少两条路径经过，那么交换这两组匹配；若一条边 \(sz\) 较小的那棵子树内有一对不出子树的匹配，那么对于 \(sz\) 较大的那棵子树内也一定有这样的匹配，那么交换这两组匹配。调整次数是有限的，因为 \(k\) 都在严格地朝目标方向变化。
通过证明，我们也可以得到另一个观察：当 \(k\) 取到上界时，任意两组匹配对应的路径都有交，可以推出所有匹配对应的路径都有交，然后得到这个交点就是重心。
从另一个角度看，我们把该树看作以重心为根的有根树，那么我们要最大化 \(\sum_{(a,b)\in M}d_a+d_b-d_{lca(a,b)}\)，而显然容易做到每组 \(d_{lca(a,b)}\) 都等于 \(0\)。
同时，因为一组匹配可以通过第二段中所述的 “调整法” 变成上下确界的解，而一次调整必使 \(k\) 改变偶数，那么我们得到某个 \(k\) 有解的必要条件是 \(k\equiv k_L\equiv k_R\pmod 2\)。
猜想任意一个满足上述条件的 \(k\) 都存在解。考虑如何构造：一个思路是从上下界开始，利用第二段中所述的 “调整法” 调整到我们要找的解。例如，从上界开始，每次找两条交为 \(1\) 的路径，并把它们交换，使 \(k\) 减少 \(2\)。但发现这并不好做：首先我们要找到一种调整方案，使得每次都能找到两条交为 \(1\) 的路径，直到我们要的 \(k\) 为止（更极端地，直到达到下界为止）；其次，调整过程如果不能加速的话，该算法的时间也是不可承受的。
题解是归纳地构造：考虑每次找到 lca 深度最大的两个点，把它们匹配，并把它们从树中删除（删除它们后树肯定仍然连通），直到再匹配就要使得当前的 \(k\) 大于剩下的树的 \(k\) 的上界为止，此时我们再特殊地考虑一下怎么构造。可以证明这种方法其实就是构造下界的一种方法，所以它是正确的。而且注意到，只要我们每次都从当前根的子树大小最大的那个子树内选，树的重心就一直不会变，那么 \(k\) 的上界也好维护。
类似地我们有另一种方法：考虑每次选择两个 lca 为根的叶子，把它们匹配，并把它们从树中删除，直到再匹配就要使当前 \(k\) 小于剩下的树的 \(k\) 的下界为止，此时我们再特殊地考虑一下怎么构造。注意每次选择不能乱选，要保证其中一个叶子是在当前根的子树大小最大的那个子树内，否则这个方法并不能达到上界。
试着写的后面一种方法。具体在最后怎么特殊构造：假设矛盾的两个点分别为 \(a,b\)，它们之间路径长度为 \(l\)，上面的 \(0,1\) 边（边两侧子树大小的奇偶性）分别有 \(n_0,n_1\) 条。那么将 \(a,b\) 匹配后，会将路径上所有边 \(0,1\) 翻转而其他边不动。因为矛盾，则有 \(k-l<k_L-n_1+n_0\)，即 \(2n_0>k-k_L\)。那么我们考虑调整 \(a,b\)，使得 \(a,b\) 匹配后，剩下的 \(k\) 恰好是剩下的树的 \(k_L'\)。这意味着对于新的 \(a,b\) 而言，有 \(k-l=k_L-n_1+n_0\)，即 \(2n_0=k-k_L\)。于是我们将 \(a,b\) 不断往父亲跳，直到该条件恰好满足为止，然后将它们匹配。然后对于剩下的点跑一遍 dfs 构造下界 \(k_L'\) 的方案。
需要实现到根链异或和到根链求和，写的粗糙了些，用树剖实现，时间复杂度 \(O(n\log^2n)\)。
#include<bits/stdc++.h>
#define N 100010
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
ll k;
int n,rt;
int cnt,head[N],to[N<<1],nxt[N<<1];
int idx,d[N],fa[N],size[N],son[N],top[N],id[N],rk[N];
int du[N],srt[N];
bool match[N];
void adde(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void findroot(int u,int fa)
{
size[u]=1;
int nmax=0;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa) continue;
findroot(v,u);
size[u]+=size[v];
nmax=max(nmax,size[v]);
}
nmax=max(nmax,n-size[u]);
if((nmax<<1)<=n) rt=u;
}
void dfs(int u)
{
size[u]=1;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa[u]) continue;
du[u]++,d[v]=d[u]+1,fa[v]=u;
dfs(v),size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
void dfs1(int u,int tp)
{
top[u]=tp;
rk[id[u]=++idx]=u;
if(son[u]) dfs1(son[u],tp);
for(int i=head[u];i;i=nxt[i])
if(to[i]!=fa[u]&&to[i]!=son[u])
dfs1(to[i],to[i]);
}
queue<int> q[N];
void dfs2(int u)
{
bool leaf=1;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa[u]) continue;
leaf=0,srt[v]=srt[u],dfs2(v);
}
if(leaf) q[srt[u]].push(u);
}
struct data
{
int n[2];
data(){}
data(int a,int b){n[0]=a,n[1]=b;}
data operator + (const data &a){return data(n[0]+a.n[0],n[1]+a.n[1]);}
void operator += (const data &a){(*this)=(*this)+a;}
void swap(){std::swap(n[0],n[1]);}
};
namespace Seg
{
data s[N<<2];
bool rev[N<<2];
void up(int k){s[k]=s[k<<1]+s[k<<1|1];}
void build(int k,int l,int r)
{
if(l==r)
{
s[k].n[size[rk[l]]&1]++;
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
up(k);
}
void downn(int k){s[k].swap(),rev[k]^=1;}
void down(int k)
{
if(rev[k])
{
downn(k<<1),downn(k<<1|1);
rev[k]=0;
}
}
void update(int k,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)
{
downn(k);
return;
}
down(k);
int mid=(l+r)>>1;
if(ql<=mid) update(k<<1,l,mid,ql,qr);
if(qr>mid) update(k<<1|1,mid+1,r,ql,qr);
up(k);
}
data query(int k,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr) return s[k];
down(k);
int mid=(l+r)>>1;
if(qr<=mid) return query(k<<1,l,mid,ql,qr);
if(ql>mid) return query(k<<1|1,mid+1,r,ql,qr);
return query(k<<1,l,mid,ql,qr)+query(k<<1|1,mid+1,r,ql,qr);
}
}
data query(int a)
{
data ans(0,0);
while(top[a]!=rt)
{
ans+=Seg::query(1,1,n,id[top[a]],id[a]);
a=fa[top[a]];
}
if(a!=rt) ans+=Seg::query(1,1,n,id[rt]+1,id[a]);
return ans;
}
void update(int a)
{
while(top[a]!=rt)
{
Seg::update(1,1,n,id[top[a]],id[a]);
a=fa[top[a]];
}
if(a!=rt) Seg::update(1,1,n,id[rt]+1,id[a]);
}
int dfs3(int u)
{
vector<int> p;
if(!match[u]) p.push_back(u);
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa[u]) continue;
int tmp=dfs3(v);
if(tmp) p.push_back(tmp);
}
int sp=p.size();
for(int i=0;i+1<sp;i+=2)
printf("%d %d\n",p[i],p[i+1]);
return (sp&1)?p[sp-1]:0;
}
int main()
{
scanf("%d%lld",&n,&k);
for(int i=1;i<n;i++)
{
int u=read(),v=read();
adde(u,v),adde(v,u);
}
findroot(1,0);
dfs(rt);
ll kl=0,kr=0;
for(int i=1;i<=n;i++)
kl+=(size[i]&1),kr+=d[i];
assert((kl&1)==(kr&1));
if(k<kl||k>kr||((kl&1)^(k&1)))
{
puts("NO");
return 0;
}
puts("YES");
dfs1(rt,rt);
Seg::build(1,1,n);
assert(kl==Seg::s[1].n[1]);
set<pair<int,int>> s;
for(int i=head[rt];i;i=nxt[i])
{
int v=to[i];
s.insert(make_pair(size[v],v));
srt[v]=v,dfs2(v);
}
s.insert(make_pair(0,0));
while(1)
{
assert(Seg::s[1].n[1]<=k);
auto it=s.end();
--it; int sA=(*it).first,A=(*it).second;
--it; int sB=(*it).first,B=(*it).second;
if(!sB)
{
assert(sA==1);
printf("%d %d\n",rt,q[A].front());
return 0;
}
int a=q[A].front(); q[A].pop();
int b=q[B].front(); q[B].pop();
auto ps=query(a)+query(b);
if((ps.n[0]<<1)>k-Seg::s[1].n[1])
{
if(!(k-Seg::s[1].n[1]))
{
assert(!dfs3(rt));
return 0;
}
int n0=ps.n[0];
while(a!=rt&&(n0<<1)>k-Seg::s[1].n[1])
{
n0-=Seg::query(1,1,n,id[a],id[a]).n[0];
a=fa[a];
}
while(b!=rt&&(n0<<1)>k-Seg::s[1].n[1])
{
n0-=Seg::query(1,1,n,id[b],id[b]).n[0];
b=fa[b];
}
assert((n0<<1)==k-Seg::s[1].n[1]);
printf("%d %d\n",a,b);
match[a]=match[b]=1;
assert(!dfs3(rt));
return 0;
}
printf("%d %d\n",a,b);
match[a]=match[b]=1;
update(a),update(b);
k-=d[a]+d[b];
if(!(--du[fa[a]])) q[A].push(fa[a]);
if(!(--du[fa[b]])) q[B].push(fa[b]);
s.erase(make_pair(sA,A)),s.insert(make_pair(sA-1,A));
s.erase(make_pair(sB,B)),s.insert(make_pair(sB-1,B));
}
return 0;
}