题解区似乎没有和我相同的做法，那我来补一个很自然的做法。
题目链接。
题意
给定一棵
个点的树，称两条边相邻当且仅当这两条边有公共端点。
你需要按某种顺序删掉树上的
条边，每一次删的边需要保证，剩余的其他边中，和这条边相邻的恰好有偶数条。
判断无解或构造方案。
。
题解
下文中，树上某条路径的距离或长度，均指这条路径上的边数。
直接想比较困难，先来考虑一条链的情况。
手玩可以发现，当且仅当链的长度为奇数的时候有解。
证明很简单，首先
有解，剩下的可以归纳法证：
对于长为奇数的链，先拿走第二条边，就可以分成两个奇数的小链，有解。
对于长为偶数的链，无论拿走哪一条边，都会产生另外一条偶数的链，所以无解。
再来考虑树的情况，手玩样例，大胆猜测：
对于一棵树，有解的充要条件是，其可以划分为若干条长度为奇数的链，使得所有链没有共同的端点（即一个点最多作为一条链的一端）。
证明分为两部分：有解的树一定满足上面的条件，和上面的条件有解，两部分都不难。先来证明第一部分。
首先有一些显然的结论，设 为
这个点的度数。
那么当 为奇数的时候， 一定为某条链的端点（否则一条链只会对
造成偶数个度数， 应该为偶数）。
当 为偶数的时候， 一定不是任何链的端点（否则 一定作为 条链的端点，不符合条件）。
使用归纳法证明，
的时候成立（划分为
条链，显然我们可以认为所有链长度都是奇数）。
当
的时候，考虑任何一组解删去的第一条边，设这条边为 。
当 与 都是奇数的时候，我们可以将 看作是一条长度为
的链，此时我们将整棵树划分为两部分。
而删去这条边之后， 与 都是偶数， 和
就不可能是其他链的端点，满足一个点最多是一个链端点的假设。
所以只需要划分为的两部分都有解，这棵树就满足我们的条件。
而对于一棵有解的树，这两部分显然都有解。
当 与 都是偶数的时候，考虑先删去 这两条边，对两棵子树分别构造。
删去这条边后，对这两部分来说， 和
都是奇数，那么他们应各是一条奇数链的端点。
而两条奇数链和一条边拼一起，还是一条奇数链，这样我们就递归完成了构造。
所以如果划分为的两部分都有解，我们还是能够将整棵树划分为若干条端点不同的奇数链。
综上所述，无论是那种情况，我们都能对分成的两棵子树分别构造，然后进行合并。
所以我们使用归纳法证明了，如果有解，那么一定整棵树一定可以划分为若干条链，使得所有链端点互不相同。
假设我们已经将这棵树划分为若干奇数链，考虑如何构造一组解。
考虑每一次删除一条完整的链（链内部的顺序，与单链相同），这样我们就不需要考虑某条链删了一般的情况了。
考虑什么时候，删除一条链是合法的。
容易发现，条件共有 个。
- 对于当前链的端点，这个点的度数是奇数。
- 对于当前链的中间点，这个点的度数是偶数。
对于链的端点来说，由于没有某条链删了一般的情况，所有链的端点也互不重合，可以发现第
个条件一直满足。
对于链的中间点来说，可以发现，若另外一条链穿过了它，只会对度数造成
（偶数）的贡献，没有影响。所以我们只需要考虑这个点作为其他链的顶点的情况。
整理一下，可以发现条件为，链上每一点都不是其他链的端点。
那么我们显然可以构造一组合法的删链顺序。
对于一个点来说，我们可以先递归构造其所有子树的方案，然后在根的位置合并即可（优先删掉，根作为端点的链在的子树）。
这样我们就证明了，满足条件的树一定有解。
具体实现：
首先我们需要把整棵树划分为若干长度为奇数的链。
这个可以直接
dfs，然后在每一个点贪心合并所有儿子传上来的链即可（显然，一个儿子会传上来恰好一条链，所以这部分不难）。
对于确定删链的顺序来说，上面讲的构造是可行的，但其实还有另一种方法，就是拓扑排序，可能相对来说更好写。
代码
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
template<const int N,const int M>
struct graph
{
int head[N+5];
int t[M+5];
int x[M+5];
int cntm;
graph(){ cntm=1;}
inline void clear(int n=N)
{
cntm=1;
for(int i=1;i<=n;i++) head[i]=0;
}
inline void ad(int u,int v)
{
cntm++;
t[cntm]=v;
x[cntm]=head[u];
head[u]=cntm;
}
inline void add(int u,int v)
{
ad(u,v);
ad(v,u);
}
inline int st(int num){ return head[num];}
inline int to(int num){ return t[num];}
inline int nx(int num){ return x[num];}
};
graph<200000,400000>g;
vc<int>e[400001];
vc<int>nod[200001];
int fa[200001];
int dep[200001];
int mat[200001];
int in[400001];
int u[200001];
int v[200001];
int p[200001];
int d[200001];
bool f;
int n,c;
int dfs(int num)
{
set<int>ji,ou;
for(int i=g.st(num);i;i=g.nx(i))
{
int p=g.to(i);
if(p==fa[num]) continue;
fa[p]=num,dep[p]=dep[num]+1;
int val=dfs(p);
if((dep[val]-dep[num])%2==0)
{
if(ji.size())
{
int id=*(ji.begin());
mat[val]=id,mat[id]=val;
ji.erase(id);
}
else ou.insert(val);
}
else
{
if(ou.size())
{
int id=*(ou.begin());
mat[val]=id,mat[id]=val;
ou.erase(id);
}
else ji.insert(val);
}
}
if(num==1)
{
if(ji.size())
{
int id=*(ji.begin());
mat[1]=id,mat[id]=1;
ji.erase(id);
}
if(ji.size()||ou.size()){ f=0;return -1;}
return 1;
}
if(ji.size()+ou.size()>2||ou.size()==2)
{
f=0;
return num;
}
if(ji.size()==2)
{
int id1=*(ji.begin());
int id2=*(++ji.begin());
mat[id1]=num,mat[num]=id1;
return id2;
}
int ans=num;
if(ji.size()) ans=*(ji.begin());
if(ou.size()) ans=*(ou.begin());
return ans;
}
inline int lca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
while(dep[u]>dep[v]) u=fa[u];
while(u!=v) u=fa[u],v=fa[v];
return u;
}
inline void add(int u,int v)
{
in[v]++;
e[u].push_back(v);
}
inline void run(int id)
{
int now=u[id];vc<int>num;
while(now!=p[id]) nod[id].push_back(now),now=fa[now];
nod[id].push_back(p[id]),now=v[id];
while(now!=p[id]) num.push_back(now),now=fa[now];
reverse(num.begin(),num.end());
for(int i:num) nod[id].push_back(i);
for(unsigned i=0;i<nod[id].size();i++)
{
if(i==0||i+1==nod[id].size()) add(id+n,nod[id][i]);
else add(nod[id][i],id+n);
}
}
inline void cover(int id)
{
for(unsigned i=1;i<nod[id].size();i+=2)
{
if(i+1<nod[id].size()) printf("%d %d\n",nod[id][i],nod[id][i+1]);
printf("%d %d\n",nod[id][i],nod[id][i-1]);
}
}
inline void topo()
{
queue<int>que;
for(int i=1;i<=n+c;i++) if(!in[i]) que.push(i);
while(!que.empty())
{
int u=que.front();que.pop();
if(u>n) cover(u-n);
for(int i:e[u])
{
in[i]--;
if(!in[i]) que.push(i);
}
}
}
int main()
{
int T=read();
while(T--)
{
g.clear(n),n=read(),f=1,c=0;
for(int i=1;i<=n;i++) mat[i]=d[i]=0;
for(int i=1;i<n;i++)
{
int u=read(),v=read();
d[u]++,d[v]++;
g.add(u,v);
}
if(dfs(1)!=1||!f)
{
printf("NO\n");
continue;
}
for(int i=1;i<=n+c;i++) in[i]=0,e[i].clear();
printf("YES\n");
for(int i=1;i<=n;i++) if(mat[i]>i)
{
c++;
u[c]=i,v[c]=mat[i];
p[c]=lca(u[c],v[c]);
nod[c].clear();
in[n+c]=0,e[n+c].clear();
run(c);
}
topo();
}
return 0;
}
|
感谢观看！