萌新求调,很神奇地第二个点case 6 wa
查看原帖
萌新求调,很神奇地第二个点case 6 wa
801322
Womind楼主2023/10/12 10:58

原因是修改后不是树。但是我想树上删一条边后再用删掉边的点新建一条边,应该不会有环吧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;
	} 

}
2023/10/12 10:58
加载中...