chtholly-daisuki的小屋

「器用贫乏」

0%

cd round 1060 D 题解

发表于 分类于 ， ，

一道答案构造比较难想的图论题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<bits/stdc++.h>
using namespace std;
#define maxn 200010
#define MOD 998244353
#define ll long long

struct edge{
	int u,v;
};
vector<edge> e;
vector<int> p[maxn];
int pre[maxn],dis[maxn],oud[maxn];//前缀，距离，出度，已删除 
int leaf[2][maxn],cnt[2];//现有的出度为1的叶子结点，0为偶，1为奇 
bool del[maxn];
int delcnt=0;//通过操作二删除的叶子结点 
bool vis[maxn];
int ans[4*maxn],anslen=0;
int n;
void dfs(int x){
	//cout<<"tar:"<<x<<endl;
	//oud[x]=1;
	/*if(p[x].size()==1){//bug2: debugtime:7min
		leaf[dis[x]%2][++cnt[dis[x]%2]]=x;
		return oud[x];//叶子结点 
	}*/
	int xcnt=0;
	for(int i=0;i<p[x].size();i++){
		int np=e[p[x][i]].v;
		if(vis[np]) continue;
		xcnt++;
		dis[np]=dis[x]+1;
		vis[np]=1;
		//oud[x]+=dfs(np); bug3:debugtime:10min出度，不是子节点数目！！ 
		dfs(np);
	}
	if(xcnt==0){
		leaf[dis[x]%2][++cnt[dis[x]%2]]=x;
		oud[x]=1;//叶子结点 
	}else{
		//oud[x]=2;//bug4 debugtime:5min多个出边！！ 
		oud[x]=1+xcnt;
	}
}
void outleaf(){
	for(int i=0;i<=1;i++){
		for(int j=1;j<=cnt[i];j++){
			cout<<"leaf:"<<i<<","<<leaf[i][j]<<endl;
		}
	}	
}
void out(){
	for(int i=1;i<=n;i++){
		cout<<i<<":"<<dis[i]<<","<<oud[i]<<"#"<<vis[i]<<endl;
	}
	cout<<endl;
}
int main() {
	//cout<<!(82%2)<<":"<<!(81%2);
	
	int t;
	cin>>t;
	while(t--) {
		
		cin>>n;
		for(int i=1;i<=n-1;i++){
			int uu,vv;
			cin>>uu>>vv;
			e.push_back(edge{uu,vv});
			e.push_back(edge{vv,uu});
		} 
		for(int i=0;i<e.size();i++){
			p[e[i].u].push_back(i);
		}
		//out();
		dis[n]=1;
		vis[n]=1;
		dfs(n);
		//out();
		int cntans=0,sumans=0;
		int cntm=0+dis[1]%2;//cnt-move bug5:dis是从n开始算的，但貓是从1开始走的
		//所以奇偶性染色应该以1为初始开始染 
		while(delcnt<=n-2){//一层循环删除一个节点 
			//cout<<"------------------"<<delcnt<<endl;
			//恶心点：要提前输出操作次数 ?????
			//cout<<1<<endl;
			ans[++cntans]=-1;cntm++;sumans++;
			if(cnt[!(cntm%2)]==0){//bug1 !(cntm%2): debugtime:4min删除奇偶性不同的点 
				ans[++cntans]=-1;cntm++;sumans++;
				//cout<<1<<endl;
			}
			int delp=leaf[!(cntm%2)][cnt[!(cntm%2)]];//要删除的节点
			del[delp]=1;
			cnt[!(cntm%2)]--;
			delcnt++;
			//cout<<"cntm:"<<cntm<<endl;
			//cout<<"2 "<<delp<<endl;
			ans[++cntans]=delp;
			for(int i=0;i<p[delp].size();i++){
				int np=e[p[delp][i]].v;
				//cout<<delp<<"=>"<<np<<endl;
				if(del[np]||np==n) continue;//已被删除
				oud[np]--;
				if(oud[np]==1){//&&np!=n?
					leaf[dis[np]%2][++cnt[dis[np]%2]]=np;//
				}
			}
			//outleaf();
		}
		cout<<cntans<<endl;
		for(int i=1;i<=cntans;i++){
			if(ans[i]==-1){
				cout<<1<<endl;
			}else{
				cout<<"2 "<<ans[i]<<endl; 
			}
		}
		e.clear();
		for(int i=0;i<=n;i++){
			p[i].clear();
			pre[i]=0;dis[i]=0;oud[i]=0;
			vis[i]=0;
			del[i]=0;
			leaf[0][i]=0;leaf[1][i]=0;
		}
		for(int i=1;i<=3*n;i++){
			ans[i]=0;
		}
		delcnt=0;cnt[0]=0;cnt[1]=0;
		anslen=0;
		cout<<endl;
		//cout<<"****************************"<<endl;
	}
	return 0;
}