AB 略

C

对于ax+ay+az>max(2*az,an)，枚举y z 二分x

D

首先，长度为1的边的已经有n-1条，那么构造的图中只能存在一条长度为2的好边。我们先构造出一个图只存在n-1条好边，我们发现对于一个点所有连接它的边要不均指向它要不均背离它。我们的目标变为寻找长度为2的边的中点，发现反转相连的一条边后当且仅当这个点的度数为2时可以只新增一条边长为二的边。没有则不存在

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,mod=998244353;
int T,n,ans[N][2],cnt,k,du[N];
vector<int> son[N];
void init()
{for(int i=1;i<=n;i++){du[i]=0;son[i].clear();}cnt=k=0;
}
void dfs(int x,int fa,int t)
{for(int i=0;i<son[x].size();i++){int y=son[x][i];if(y==fa) continue;if(t==1) ans[++cnt][0]=x,ans[cnt][1]=y;else ans[++cnt][0]=y,ans[cnt][1]=x;dfs(y,x,1-t);}
}
void solve()
{cin>>n;init();for(int i=1;i<n;i++){int x,y;cin>>x>>y;son[x].push_back(y);son[y].push_back(x);du[x]++;du[y]++;}for(int i=1;i<=n;i++)if(du[i]==2) k=i;if(n==2||!k) {cout<<"NO"<<endl; return ;}int t1=son[k][0],t2=son[k][1];ans[++cnt][0]=t1,ans[cnt][1]=k;ans[++cnt][0]=k,ans[cnt][1]=t2;dfs(t1,k,1);dfs(t2,k,0);cout<<"YES"<<endl;for(int i=1;i<n;i++)cout<<ans[i][0]<<" "<<ans[i][1]<<endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie();cout.tie();cin>>T;while(T--) solve();
}​