「Codeforces #573C」Bear and Drawing

失去思维能力

Codeforces #573C

题意

给出\(n\)个点的树,问能否边不相交地画在两行平行的点上,\(n\le 10^5\)


分析

问题可以转化为以下条件

  1. 有一条主链,主链上的点无度数限制

  2. 和主链直接相连的点的度数\(\le 3\)

  3. 其他点度数\(\le 2\)


实现

只考虑度数\(\le 2\)的点,把和度数\(=1\)的叶子连通的这些点全部删掉。

重新统计度数

把原先度数\(=3\)的点,新度数\(=1\)的点删掉

重新统计度数

这时候应该只剩下一条主链,检验是否有点的度数\(>2\)即可

复杂度 \(\mathcal O(n)\)


代码

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
#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig = false, c = read(); !isdigit(c); c = read()) {
if (c == '-') iosig = true;
if (c == -1) return;
}
for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
if (iosig) x = -x;
}
const int N = 100005;
int n, ans, num, tot, h[N], d[N], dd[N], e[N<<1], pre[N<<1];
bool vis[N];
inline void add(int x, int y){ e[++num]=y, pre[num]=h[x], h[x]=num;}
void dfs(int u){
vis[u]=1;
for(int i=h[u]; i; i=pre[i]) if(d[e[i]]==2 && !vis[e[i]]) dfs(e[i]);
}
int main() {
read(n);
for(int i=1; i<n; ++i){
static int x, y;
read(x), read(y);
add(x, y), add(y, x), ++d[x], ++d[y];
}
for(int i=1; i<=n; ++i) if(d[i]==1) dfs(i);
memcpy(dd, d, sizeof d);
for(int i=1; i<=n; ++i) if(vis[i]) for(int j=h[i]; j; j=pre[j]) --d[e[j]];
for(int i=1; i<=n; ++i) if(dd[i]==3 && d[i]==1) for(int j=h[i]; j; j=pre[j]) --d[e[j]];
int mx=0;
for(int i=1; i<=n; ++i) mx=max(mx, d[i]);
return puts(mx<=2?"Yes":"No"), 0;
}