原因是修改后不是树。但是我想树上删一条边后再用删掉边的点新建一条边,应该不会有环吧QwQ 代码呈上 Orz
/*
Name:
Copyright:
Author:
Date: 2023/10/12 9:51:06
Description:
*/
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repe(i,a,b) for (int i = (a); i >= (b); i--)
const int N = 1e5 + 1;
int t, n;
int head[N], nxt[N << 1], to[N << 1], cnt = 0, from[N << 1];
int siz[N];
bool flag = 0;
void dfs(int u, int fa) {
siz[u] = 1;
for(int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v == fa) continue;
dfs(v, u);
siz[u] += siz[v];
}
if (flag ) return;
if (siz[u] == n - siz[u]) {
int v = to[head[u]];
cout << u << " " << v << endl;
cout << v << " " << fa << endl;
flag = 1;
}
}
int main(){
cin >> t;
while (t--) {
cin >> n;
flag = 0; cnt = 0;
rep(i, 1, n - 1) {
int x, y;
scanf("%d%d", &x, &y);
nxt[++cnt] = head[x]; to[cnt] = y; head[x] = cnt; from[cnt] = x;
nxt[++cnt] = head[y]; to[cnt] = x; head[y] = cnt; from[cnt] = y;
}
if (n % 2) {
printf("%d %d\n%d %d\n", from[1], to[1], from[1], to[1]);
// 一条已知边 必须是树
rep(i,1,n) head[i] = 0;
rep(i,1,2 * n) nxt[i] = to[i] = 0;
continue;
}
dfs(1, 0);
if (flag == 0) printf("%d %d\n%d %d\n", from[1], to[1], from[1], to[1]);
rep(i,1,n) head[i] = 0;
rep(i,1,2 * n) nxt[i] = to[i] = 0;
}
}