Description
众所周知，圣诞树是一棵 $n$ 个节点的树。
这意味着它将包含很多割点，这导致了结构不稳定。你需要为它添加一些边，使得割点不存在。
给出你的加边方案。
Idea
我们可以先考虑如果是割边的话应该怎么做。显然答案下界是 $\lceil \dfrac{l}{2} \rceil$ ，其中 $l$ 是叶节点个数
我们可以构造出这样的⽅案：令叶节点的权值为 1 ，⾮叶节点的权值为 0 ，求整棵树的带权重⼼ $c$。由于重⼼的每个⼉⼦的⼦树⾥都只有不超过 $\lfloor \dfrac{c}{2} \rfloor$ 个叶⼦，我们不难构造出⼀组⽅案使得每条边连接的两个叶⼦都来⾃于重⼼的不同⼉⼦的⼦树。
考虑割点。显然答案下界是 $\max(\max\{d_i\}-1,\lceil \dfrac{l}{2} \rceil)$ ，其中 $d_i$ 是点 $i$ 的度数。我们可以构造出这样的⽅案：注意到之前的⽅案⾥除了重⼼之外，每个点都保证了删掉它后，它的所有⼉⼦的⼦树依然是与重⼼所在的连通块连通的，固整个图也是连通的。
Code
#include <bits/stdc++.h>
#define maxn 500100
#define max(a,b) (a>b?a:b)
#define pb push_back
using namespace std;
vector<int> s[maxn];
priority_queue<pair<int,int> >q;
int siz[maxn],lea[maxn],mx[maxn];
int n,son,cnt,head[maxn],deg[maxn];
int ans,con[maxn][2];
int read(){
int x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x*flag;
}
struct Edge{
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
void wipe(){
to=next=0;
}
}l[maxn<<1];
void Add(int a,int b){
l[++cnt]=Edge(b,head[a]);head[a]=cnt;
l[++cnt]=Edge(a,head[b]);head[b]=cnt;
}
bool Compare(vector<int> a,vector<int> b){
return a.size()>b.size();
}
void Pre(int u,int f){
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==f) continue;
Pre(v,u);siz[u]+=siz[v];
mx[u]=max(mx[u],siz[v]);
}
}
void Dfs(int u,int f){
if (lea[u]) s[son].pb(u);
for (int i=head[u];i;i=l[i].next)
if (l[i].to!=f) Dfs(l[i].to,u);
}
void New(int a,int b){
con[++ans][0]=a,
con[ans][1]=b;
}
void Update(int u){
s[u].pop_back();
if (!s[u].empty())
q.push(make_pair(s[u].size(),u));
}
void Solve(){
for (int i=1;i<=n;++i)
lea[i]=deg[i]=head[i]=mx[i]=siz[i]=0;
for (int i=1;i<=n;++i)
l[i].wipe();
for (int i=1;i<=son;++i)
s[i].clear();
n=read();ans=cnt=son=0;
for (int i=1,a,b;i<n;++i)
a=read(),b=read(),Add(a,b),
deg[a]++,deg[b]++;
for (int i=1;i<=n;++i)
if (deg[i]==1) lea[i]=1,siz[i]++;
Pre(1,0);
int rt=1;
for (int i=2;i<=n;++i){
mx[i]=max(mx[i],siz[1]-siz[i]);
if (mx[i]<mx[rt]) rt=i;
}
for (int i=head[rt];i;i=l[i].next)
son++,Dfs(l[i].to,rt);
sort(s+1,s+1+son,Compare);
int fst=s[1].back();
q.push(make_pair(s[1].size(),1));
for (int i=2;i<=son;++i){
if (s[i].empty()) continue;
if (q.empty()) New(s[i].back(),fst);
else{
int cur=q.top().second;q.pop();
New(s[cur].back(),s[i].back());
Update(cur);
}
Update(i);
}
while(!q.empty()){
int a=q.top().second;q.pop();
if (q.empty()){New(s[a].back(),fst);break;}
int b=q.top().second;q.pop();
New(s[a].back(),s[b].back());
Update(a),Update(b);
}
printf("%d\n",ans);
for (int i=1;i<=ans;++i)
printf("%d %d\n",con[i][0],con[i][1]);
}
int main(){
int T=read();
while(T--) Solve();
}