原題鏈接

解析

不難發現對于一條鏈，直接從一個端點 check 到另一個就可以。進而發現如果要保證找到，那么每個點都需要 check 一次。結合操作次數的限制，問題變成了用不超過 \(\lfloor \frac{n}{4}\rfloor\) 次操作 2 把樹分割成若干條鏈。

于是就會有一個想法，對于所有兒子個數為 2 的點，讓它對兩個兒子子樹中導出的鏈進行連接，這意味著父親必須斷邊，而對于所有的兒子個數大于等于 \(3\) 的點，對其斷邊，當然斷邊之后就不算是父親的兒子了。那么最壞情況就是每四個點做一次操作，滿足 \(\lfloor \frac{n}{4}\rfloor\) 的限制。

代碼

感覺寫得一坨，不建議看。

/*
*/
#include<bits/stdc++.h>
#define eps 0.000001
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll,int> pii;
const int N = 2e5 + 5,M = 3.2e4 + 5;
vector<int> t[N];
bool op[N],ist[N];
int k,f[N],lf[N],cnt[N]; 
vector<int> v;
struct S{
	int u,v,tp;
};
vector<S> lst;
void dfs(int x,int fa){
	f[x] = fa;
	bool tp = false;
	vector<int> pos; 
	for(int nx : t[x])if(nx != fa){
		dfs(nx,x);
		cnt[x] += !op[nx];
		tp |= ist[nx];
		if(!op[nx]){
			pos.push_back(lf[nx]);
		}
	}
	if(!cnt[x]) lf[x] = x; 
	else if(pos.size() == 1) lf[x] = pos[0];
	if(cnt[x] >= 3 || tp){
		op[x] = true;
		for(int nx : t[x])if(nx != fa && !op[nx] && cnt[nx] <= 1){
			lst.push_back({lf[nx],nx,nx});
		}
		v.push_back(x);
		k++;	
	}else if(cnt[x] == 2){ 
		lst.push_back({pos[0],pos[1],x});
		ist[x] = true;
	}else if(cnt[x] == 1 && x == 1){
		lst.push_back({pos[0],x,x});
	}
}
void print(int x,int tp){
	cout<<1<<" "<<x<<'\n';
	if(x == tp) return;
	print(f[x],tp);
}
void rprint(int x,int tp){
	if(x == tp) return;
	rprint(f[x],tp);
	cout<<1<<" "<<x<<'\n';
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out1.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		k = n;
		for(int i=1;i<n;i++){
			int u,v;
			cin>>u>>v;
			t[u].push_back(v);
			t[v].push_back(u);
		}
		dfs(1,0);
		cout<<k<<'\n';
		for(int i : v){
			cout<<2<<" "<<i<<'\n';
		}
		for(int i : v){
			cout<<1<<" "<<i<<'\n';
		}
		for(S l : lst){
			print(l.u,l.tp);
			rprint(l.v,l.tp);
		}
		if(!cnt[1]) cout<<1<<" "<<1<<'\n';
		lst.clear();
		v.clear();
		for(int i=1;i<=n;i++){
			lf[i] = 0;
			t[i].clear();
			ist[i] = false;
			cnt[i] = 0;
			op[i] = 0;
		}
	} 
	return 0;
}
/*
*/