Siyuan

「Codeforces 1189D1」Add on a Tree
「Codeforces 1189D1」Add on a Tree
扫描右侧二维码阅读全文
05
2019/08

「Codeforces 1189D1」Add on a Tree

题目链接:Codeforces 1189D1

你有一个棵 $n$ 个点的树,初始所有的边上的数字都是 $0$。对于每次操作,你可以选择两个不同的叶子节点 $u,v$ 和一个任意实数 $x$ 并把 $u - v$ 这条简单路径上的边加上 $x$。

我们令 $w_{i}$ 表示最终第 $i$ 条边上的实数,是否对于所有的 $w_{i} \in \mathbf{R}, 1 \le i < n$,都存在有限的操作使得所有的边都满足条件?如果可行则输出 YES 否则输出 NO

注意叶子节点的定义为度数为 $1$ 的点。

数据范围:$2 \le n \le 10 ^ {5}$。


Solution

设 $deg_{i}$ 表示第 $i$ 个点的度数。

首先给出结论:对于任意情况都有解的充要条件是不存在度数为 $2$ 的点

接下来分两部分证明。

必要性

如果 $deg_{i} = 2$,那么其相邻的两条边的值一定永远相等。

充分性

接下来需要证明一定存在一个操作序列可以修改某一条边的值(注意:不能破坏其他的边)。

我们随意钦定一个叶子节点为(具体原因下文会讲),那么对于每个点 $u$,我们只需要修改它和父亲的连边 $i$。由于选择的点一定是叶子节点,所以我们要把所有的修改往叶子节点上靠拢。

对于边的修改,可以转化为两条到根的路径的修改。这样我们的问题转化为将 $rt - u$ 路径上的边加上 $x$,这也是将根钦定为叶子的原因!

如果 $u$ 是叶子,那么直接选择 $(rt, u)$ 这一对叶子。由于 $deg_{u} \ge 3$,我们选择 $u$ 不同子树中的两个叶子 $l1, l2$,通过如下步骤可以实现 $rt - u$ 路径加 $x$ 的操作:

  1. 将 $rt - l1$ 路径上的边加上 $\frac{x}{2}$。
  2. 将 $rt - l2$ 路径上的边加上 $\frac{x}{2}$。
  3. 将 $l1 - l2$ 路径上的边减去 $\frac{x}{2}$。

至此我们就证明完了充要性。

时间复杂度:$O(n)$。


Code

#include <cstdio>

const int N = 1e5 + 5;

int n, deg[N];

int main() {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        deg[u]++, deg[v]++;
    }
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 2) {
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");
    return 0;
}

发表评论