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();
}?