题目链接：Codeforces 1189D2

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

每条边都有一个目标状态，用一个两两不同的非负偶数表示。你需要判断这个目标状态是否可以通过有限次操作达到。如果可行则输出 YES 和构造的方案；否则输出 NO。

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

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

Solution

直接采用 Codeforces 1189D1 中的结论。由于所有目标状态都是偶数，所以不需要考虑除以 $2$ 带来的影响。

这真是我写过最短的题解（雾

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

Code

#include <cstdio>
#include <algorithm>
#include <vector>
#include <tuple>

typedef std::pair<int, int> pii;

const int N = 1e3 + 5;

int n, rt, fa[N];
std::vector<int> vec[N];
std::vector<pii> e[N];
std::vector<std::tuple<int, int, int>> ans;

void addEdge(int u, int v, int w) {
    e[u].emplace_back(std::make_pair(v, w));
}
void modifyPath(int u, int x) {
    if (vec[u].size() == 1u) {
        ans.emplace_back(rt, u, x);
        return;
    }
    int l1 = vec[u][0], l2 = vec[u][1];
    ans.emplace_back(rt, l1, x / 2);
    ans.emplace_back(rt, l2, x / 2);
    ans.emplace_back(l1, l2, -x / 2);
}
void modifyEdge(int u, int x) {
    if (fa[u] == rt) {
        modifyPath(u, x);
    } else {
        modifyPath(u, x);
        modifyPath(fa[u], -x);
    }
}
void dfs(int u, int p) {
    fa[u] = p;
    for (auto [v, w]: e[u]) {
        if (v == p) continue;
        dfs(v, u);
        vec[u].emplace_back(vec[v].front());
    }
    if (vec[u].size() == 0u) vec[u].emplace_back(u);
}
void solve(int u, int p) {
    for (auto [v, w]: e[u]) {
        if (v == p) continue;
        modifyEdge(v, w);
        solve(v, u);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1, u, v, w; i < n; i++) {
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w), addEdge(v, u, w);
    }
    for (int i = 1; i <= n; i++) {
        if (e[i].size() == 2u) {
            printf("NO\n");
            return 0;
        }
    }
    for (rt = 1; e[rt].size() != 1u; rt++);
    dfs(rt, 0);
    solve(rt, 0);
    printf("YES\n%d\n", (int)ans.size());
    for (auto x : ans) {
        printf("%d %d %d\n", std::get<0>(x), std::get<1>(x), std::get<2>(x));
    }
    return 0;
}