题目链接：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;
}