Submission #44929143

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 2e5+10;

int T,n,w[MAXN],deg[MAXN],vis[MAXN],fa[MAXN],sz[MAXN],dep[MAXN],top[MAXN];

vector<int>e[MAXN],leaf;
typedef array<int,2> pr;
vector<pr>ret;

void Init(){
	rep(i,1,n){
		e[i].clear();
		deg[i] = vis[i] = fa[i] = 0;
	}
	ret.clear();
}
void output(){
	
	cout<<ret.size()<<"\n";
	for(auto [u,v] : ret)cout<<u<<" "<<v<<"\n";
	/*
	ll sum = 0;
	for(auto [u,v] : ret)sum += w[u] + w[v];
	cout<<sum<<endl;
	*/
}

void even_build(){
	int sz = leaf.size();
	rep(i,1,sz/2)ret.push_back({leaf[i-1],leaf[i+sz/2-1]});
}

void dfs(int u){
	sz[u] = 1;dep[u] = 1;

	for(auto v:e[u])if(v != fa[u] && !vis[v]){
		fa[v] = u;top[v] = top[u];
		dfs(v);
		sz[u] += sz[v];
		dep[u] = max(dep[u],dep[v]+1);
	}
	if(sz[u]==1)leaf.push_back(u);
}

void solve(){
	cin>>n;
	Init();
	rep(i,1,n)cin>>w[i];
	rep(i,1,n-1){
		int u,v;cin>>u>>v;
		e[u].push_back(v);e[v].push_back(u);
		deg[u]++;deg[v]++;
	}
	int rt = 0;rep(i,1,n)if(deg[i]>1)rt = i;
	assert(rt);

	leaf.clear();
	dfs(rt);

	if(leaf.size() % 2 == 0){ //偶数个叶子
		even_build();
		output();
		return;
	}
	
	int x = 0,y = 0;
	w[0] = 2e9;
	rep(i,1,n){
		if(w[i] < w[x])y=x,x=i;
		else if(w[i]<w[y])y=i;
	}
	assert(x&&y);

	leaf.clear();fa[x] = 0;

	for(auto u : e[x]){
		fa[u] = x;top[u] = u;
		dfs(u);
	}	

	for(auto u : leaf)if(sz[top[u]] != dep[top[u]]){ //+min w
		ret.push_back({u,x});
		int cnt = n;
		for(int p=u;deg[p] != 3;p=fa[p]){
			vis[p] = 1;
		}
		leaf.clear();

		int rt = 0;
		rep(i,1,n)if(!vis[i] && deg[i] > 1)rt = i;
		assert(rt);

		fa[rt] = 0;
		dfs(rt);

		even_build();
		output();

		return;
	}
	//必定有三条链
	assert(leaf.size() == 3);

	for(auto u : leaf)for(auto v : leaf)for(auto w : leaf){
		if(u == v || u == w || v == w)continue;
		if(top[u] != top[y])continue;
		ret.push_back({y,v});
		ret.push_back({u,w});
		output();
		return;
	}
	assert(0);
}

int main(){
	ios::sync_with_stdio(false);

	cin>>T;
	while(T--)solve();

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:96:7: warning: unused variable ‘cnt’ [-Wunused-variable]
   96 |   int cnt = n;
      |       ^~~

Judge Result