抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

Description

给定一棵树,每次操作选定两叶子节点并将路径上点权减一(操作前路径上的点权必须大于 0 ),问最后是否能使所有点权为 0

Solution

考虑一棵以 u 为根的子树。经过 u 节点的路径,无非两种:往上延伸的和内部配对的。我们设往上延伸的路径条数为 f_u ,内部消化的路径条数为 y 。则我们很容易发现:

\sum_{v\in \operatorname{son}(u)}f_v = 2y + f_u

而且

a_u = f_u + y

这样子,整棵树的 f_u 是唯一确定的。

判断合法性: 0\le f_u\le a_i 是必须满足的。其次对于我们内部两两配对的对数 y ,一定要满足:

y \le \min(\lfloor \frac{\sum{f_v}}{2}, \sum f_v - \max f_v)

这是一个经典结论,可以这么理解:下界肯定是很容易证明的,上界的存在是因为子树内不可能存在自己匹配自己的情况。所以要减去。

最后,根的 f 值必须为 0 ,叶的 f 值即为 a 值。

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
#include <cstdio>
#include <cctype>
#include <cstdlib>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)
#define GO(u) for (int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])

const int maxn = 1e5 + 5;

int read()
{
int s = 0, x = 0;
char c = getchar();
while (!isdigit(c))
x |= (c == '-'), c = getchar();
while (isdigit(c))
s = s * 10 + c - '0', c = getchar();
return x ? -s : s;
}

inline int max(int a, int b) {return a > b ? a : b;}
inline int min(int a, int b) {return a < b ? a : b;}

int n, head[maxn], to[maxn << 1], nxt[maxn << 1], cnte, deg[maxn];
int a[maxn], f[maxn], root;

void add(int u, int v)
{
++deg[v];
to[++cnte] = v;
nxt[cnte] = head[u];
head[u] = cnte;
return;
}

void dfs(int u, int fa)
{
if (deg[u] == 1)
{
f[u] = a[u];
return;
}
int s = 0, y, maxf = 0;
GO(u)
{
if (v == fa) continue;
dfs(v, u);
s += f[v];
maxf = max(f[v], maxf);
}
y = s - a[u];
f[u] = s - 2 * y;
if (f[u] < 0 || f[u] > a[u]) puts("NO"), exit(0);
if (y > min(s - maxf, s / 2)) puts("NO"), exit(0);
}

int main()
{
n = read();
FOR(i, 1, n) a[i] = read();
if (n == 2)
printf("%s\n", a[1] == a[2] ? "YES" : "NO"), exit(0);
FOR(i, 1, n - 1)
{
int u = read(), v = read();
add(u, v), add(v, u);
}
FOR(i, 1, n)
if (deg[root = i] > 1) break;
dfs(root, 0);
if (f[root] != 0) puts("NO"), exit(0);
puts("YES");
return 0;
}

评论




Blog content follows the [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en)
本站总访问量为 访客数为
Use Volantis as theme