雨天的尾巴

形式化题目

给一棵 $n$ 个点的树（点编号 $1 \sim n$ ）和 $m$ 次操作。每次操作给出 $(x, y, z)$ ，表示给路径 $x \to y$ 上（含两端）的每个点放入一袋 $z$ 类物品。全部操作结束后，对每个点输出存放次数最多的物品种类编号；若并列，输出编号最小的；若一个点没有任何物品，输出 $0$ 。

数据范围： $1 \le n, m \le 10^5$ ， $1 \le z \le 10^9$ 。

直接正解

思路

第一步：把"路径覆盖"转成"点上差分"。

如果每次操作都真的沿路径走一遍，单次最坏 $O(n)$ ，总代价 $O(nm) = 10^{10}$ ，不可接受。树的基本套路是先求出每条路径两端的 LCA，然后在点上做差分：对每次操作 $(x,y,z)$ ，

在 $x$ 、 $y$ 处给种类 $z$ 记 $+1$ ；
在 $\mathrm{lca}(x,y)$ 与它的父亲处给种类 $z$ 记 $-1$ 。

之后让每个点汇总整个子树的差分值，得到的恰好是"多少条路径覆盖了这个点、各是什么种类"。验证一下正确性：对点 $u$ 与一次操作 $(x,y,z)$ ， $x$ 、 $y$ 两个 $+1$ 与 LCA 处的 $-1$ 、LCA 父亲处的 $-1$ 相互配合—— $u$ 在路径上时恰好被计入 $+1$ ，不在路径上时正负抵消为 $0$ 。

flowchart LR
    A["一次操作 (x,y,z)"] --> B["x 处 z:+1"]
    A --> C["y 处 z:+1"]
    A --> D["L=lca(x,y) 处 z:-1"]
    A --> E["father(L) 处 z:-1"]
    B & C & D & E --> F["子树求和后<br>路径上每点得到 z:+1<br>路径外每点为 0"]

第二步：每个点要的是"众数种类"，不是计数和。

子树求和本身好办：逆 BFS 序遍历，把每个点的差分表并进父亲即可。难点在于每个点存的是"各种类各多少袋"，而 $z$ 高达 $10^9$ 、种类数可达 $10^5$ ，若每个点都开一张完整表，空间是 $O(n \cdot z)$ 级别，爆炸。

观察合并过程：一个点的表 = 自己的差分表 + 所有儿子的表。如果用每种一个下标的权值线段树来存这张表，合并两棵线段树时，只在"两边同时存在的区间"才递归，代价是 $O(\min(s_1, s_2) \log)$ （ $s$ 为节点数）——这正是经典的线段树合并。每次操作只新增 $O(\log)$ 个差分点，全部 $m$ 次操作总共只会有 $O(m \log)$ 个动态开点的节点，合并总代价被每个新节点"每向上并一次掉一层"摊住，为 $O(m \log)$ 级。

第三步：线段树节点上存什么才能 O(1) 拿众数？

这是本题最容易踩的坑。若节点只存子树计数和 sum，查询众数时每层走向 sum 更大的孩子，是错误的：sum 是区间和，右边可能有 2 个种类各 1 袋（和为 2），左边只有 1 个种类 3 袋（和为 3），但若右边和比左边大就会走错方向。正确做法是节点额外维护：

mx：该节点子树内单个叶子的最大计数；
best：取到该最大计数的叶子编号（即种类）。

插入差分点时沿路径更新叶子，再从叶子往上回推所有祖先的 (mx, best)；合并时用两棵树孩子的 (mx, best) 重算父亲。这样每个点的答案在查询时是 $O(1)$ 的：mx[根] > 0 时答案就是 kinds[best[根]]。并列取编号最小，靠"比较时取左孩子优先 + 叶子编号即离散化后的种类顺序"天然实现。

整体流程：

步骤	做法	代价
建树 + 求 LCA	BFS 定父/深，倍增表 `up[k][v]`	$O(n \log n)$
处理操作	每条路径差分成 4 个单点 $\pm 1$ ，动态开点插入对应点的线段树	$O(m \log n)$
汇总答案	逆 BFS 序：先取该点线段树根的 `best`，再 `merge` 进父亲	$O(m \log n)$ 摊还

flowchart TB
    subgraph ops["m 次操作"]
        Q1["(x1,y1,z1)"]
        Q2["(x2,y2,z2)"]
        Q3["..."]
    end
    subgraph nodes["每个树节点挂一棵动态开点线段树"]
        R1["点 x1: z1 +1"]
        R2["点 y1: z1 +1"]
        R3["点 L 与 father(L): z1 -1"]
    end
    ops -->|"每条路径拆 4 个差分点"| nodes
    nodes -->|"逆 BFS 序 merge 进父亲"| ANS["每点 O(1) 读 best<br>输出计数最大的种类"]

一个实现细节：线段树的叶子数 $K$ 不能只取"种类数"。合并时两棵树的区间必须完全一致（否则区间长度不同的两棵树无法逐层对应），而每个点的线段树在差分点插入时是按"种类数"开叶子的，若某子树只插过 1 个种类、父亲插过 3 个种类，合并就会错位。因此取 $K = \max(\text{种类数}, \lceil \log_2 n \rceil)$ ，保证所有树的区间结构一致。

代码

cpp

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:30
 * update_at: 2026-10-10 13:30
 */

// 雨天的尾巴：树上差分 + 动态开点权值线段树合并求路径众数。
// 路径 (x,y) 拆成 x+1、y+1、lca-1、lca父-1 四个差分点，
// 逆 BFS 序把子树线段树并到父亲，每个点取众数（并列取编号最小的种类）。
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXN = 100005;
const int MAXLOG = 19;                 // 2^17 > 100000
const int MAXNODE = 7200010;           // 4m 次插入，每次最多 ceil(log2 K)+1 = 18 个点

int n, m, K;
int parent[MAXN];
int depth[MAXN];
int ordArr[MAXN];
int up[MAXLOG][MAXN];
int roots[MAXN];
int ansArr[MAXN];
int qx[MAXN], qy[MAXN], qz[MAXN];
vector<int> adj[MAXN];
vector<int> kinds; // 离散化后的物品种类（升序）

// 动态开点权值线段树的静态池，0 号点是空树哨兵
int lc[MAXNODE];
int rc[MAXNODE];
int mxc[MAXNODE];
int nodeCnt = 1; // 0 号留空

int newNode() {
    int id = nodeCnt++;
    return id; // 池已清零
}

void pull(int node) { // 由左右孩子重算 node 的最大单类计数
    if (mxc[lc[node]] >= mxc[rc[node]]) mxc[node] = mxc[lc[node]];
    else mxc[node] = mxc[rc[node]];
}

int insertNode(int root, int pos, int delta) { // 给叶子 pos 加 delta
    if (root == 0) root = newNode();
    int cur = root, l = 0, r = K - 1;
    int path[MAXLOG + 2], pc = 0; // 自顶向下记录路径，最后统一回推
    path[pc++] = cur;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (pos <= mid) {
            int nxt = lc[cur];
            if (nxt == 0) { nxt = newNode(); lc[cur] = nxt; }
            r = mid;
            cur = nxt;
        } else {
            int nxt = rc[cur];
            if (nxt == 0) { nxt = newNode(); rc[cur] = nxt; }
            l = mid + 1;
            cur = nxt;
        }
        path[pc++] = cur;
    }
    mxc[cur] += delta; // 到达叶子：叶子上的计数本身就是它的 mx
    for (int i = pc - 2; i >= 0; --i) pull(path[i]);
    return root;
}

int mergeTree(int a, int b) { // 把 b 破坏式并入 a，返回新根
    if (a == 0 || b == 0) return a | b;
    if (lc[a] == 0 && rc[a] == 0) { // a 是叶子，b 同区间也必是叶子
        mxc[a] += mxc[b];
        return a;
    }
    lc[a] = mergeTree(lc[a], lc[b]);
    rc[a] = mergeTree(rc[a], rc[b]);
    pull(a);
    return a;
}

int queryMode(int root) { // 众数种类；空树返回 0（并列取左 = 编号更小的种类）
    if (root == 0 || mxc[root] == 0) return 0;
    int cur = root, l = 0, r = K - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (mxc[lc[cur]] >= mxc[rc[cur]]) { cur = lc[cur]; r = mid; }
        else { cur = rc[cur]; l = mid + 1; }
    }
    return kinds[l];
}

int lca(int u, int v, int rows) {
    if (depth[u] < depth[v]) { int t = u; u = v; v = t; }
    int diff = depth[u] - depth[v];
    for (int k = 0; k < rows; ++k) {
        if (diff >> k & 1) u = up[k][u];
    }
    if (u == v) return u;
    for (int k = rows - 1; k >= 0; --k) {
        if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
    }
    return up[0][u];
}

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0; // 空输入安全返回
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    // 从 1 号点 BFS（order 边遍历边增长，等价于队列）
    for (int i = 0; i <= n; ++i) parent[i] = 0;
    int ordCnt = 0;
    ordArr[ordCnt++] = 1;
    for (int i = 0; i < ordCnt; ++i) {
        int u = ordArr[i];
        for (int j = 0; j < (int)adj[u].size(); ++j) {
            int v = adj[u][j];
            if (v != parent[u]) {
                parent[v] = u;
                depth[v] = depth[u] + 1;
                ordArr[ordCnt++] = v;
            }
        }
    }

    // 倍增表：up[k][v] 是 v 向上跳 2^k 步到的祖先，0 号点是哨兵
    int bitlen = 0;
    while ((1 << bitlen) <= n - 1) ++bitlen; // (n-1).bit_length()
    int rows = 1 + (bitlen > 1 ? bitlen : 1);
    if (rows > MAXLOG) rows = MAXLOG;
    for (int x = 0; x <= n; ++x) up[0][x] = parent[x];
    for (int k = 1; k < rows; ++k) {
        for (int x = 0; x <= n; ++x) up[k][x] = up[k - 1][up[k - 1][x]];
    }

    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d", &qx[i], &qy[i], &qz[i]);
        kinds.push_back(qz[i]);
    }
    sort(kinds.begin(), kinds.end());
    kinds.erase(unique(kinds.begin(), kinds.end()), kinds.end());

    // 叶子数 K 必须同时 >= 种类数（装下差分点）和 n-1 的位长
    K = kinds.size();
    if (bitlen > K) K = bitlen;
    if (K == 0) K = 1;

    for (int i = 0; i < m; ++i) {
        int x = qx[i], y = qy[i];
        int kind = lower_bound(kinds.begin(), kinds.end(), qz[i]) - kinds.begin();
        int l = lca(x, y, rows);
        roots[x] = insertNode(roots[x], kind, 1);
        roots[y] = insertNode(roots[y], kind, 1);
        roots[l] = insertNode(roots[l], kind, -1);
        if (parent[l]) roots[parent[l]] = insertNode(roots[parent[l]], kind, -1);
    }

    // 逆 BFS 序：u 的树已含全部子树差分时先取答案，再并入父节点
    for (int i = n - 1; i >= 0; --i) {
        int u = ordArr[i];
        ansArr[u] = queryMode(roots[u]);
        if (parent[u]) roots[parent[u]] = mergeTree(roots[parent[u]], roots[u]);
    }

    for (int i = 1; i <= n; ++i) printf("%d\n", ansArr[i]);
    return 0;
}

python

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 00:20
# update_at: 2026-10-02 00:20

import sys


def lca(u: int, v: int, depth: list[int], up: list[list[int]]) -> int:
    """返回 u,v 的最近公共祖先（二进制提升表 up）。"""
    if depth[u] < depth[v]:  # 统一让 u 更深
        u, v = v, u
    diff = depth[u] - depth[v]
    for k in range(len(up)):
        if diff >> k & 1:  # u 上提 diff 的每个二进制位
            u = up[k][u]
    if u == v:
        return u
    for k in range(len(up) - 1, -1, -1):  # 从高位跳，落到最近公共祖先的下一层
        if up[k][u] != up[k][v]:
            u, v = up[k][u], up[k][v]
    return up[0][u]


def bfs_order(adj: list[list[int]]) -> tuple[list[int], list[int], list[int]]:
    """从 1 号点 BFS，返回 (访问顺序, 父节点, 深度)；order 边遍历边增长，等价于队列。"""
    size = len(adj)
    parent = [0] * size  # 0 号点是根的哨兵父节点
    depth = [0] * size
    order = [1]
    for u in order:
        for v in adj[u]:
            if v != parent[u]:
                parent[v] = u
                depth[v] = depth[u] + 1
                order.append(v)
    return order, parent, depth


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    adj: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        a, b = next(data), next(data)
        adj[a].append(b)
        adj[b].append(a)

    order, parent, depth = bfs_order(adj)

    up = [parent]  # up[k][v]：v 向上跳 2^k 步到的祖先，0 号点是哨兵
    for _ in range(max(1, (n - 1).bit_length())):
        prev_up = up[-1]
        up.append([prev_up[x] for x in prev_up])

    qx = [0] * m
    qy = [0] * m
    qz = [0] * m
    for i in range(m):
        qx[i] = next(data)
        qy[i] = next(data)
        qz[i] = next(data)

    kinds = sorted(set(qz))                     # 离散化：叶子编号 -> 物品种类
    rank = {z: i for i, z in enumerate(kinds)}  # 物品种类 -> 叶子编号
    # 叶子数 K 必须同时 >= 种类数（装下所有差分点）和 n-1 的位长（merge 时两树区间一致）
    K = max(len(kinds), (n - 1).bit_length())

    # 动态开点权值线段树（数组版），0 号点是空树哨兵；闭包访问比全局快
    # mx[v]：v 子树内最大的单类计数（不是区间和！）；best[v]：取到该最大值的叶子编号
    left = [0]
    right = [0]
    mx = [0]
    best = [0]

    def pull(node: int) -> None:
        """由左右孩子重算 node 的 (mx, best)；并列取左孩子 = 编号更小的种类。"""
        lc, rc = left[node], right[node]
        if mx[lc] >= mx[rc]:
            mx[node] = mx[lc]
            best[node] = best[lc]
        else:
            mx[node] = mx[rc]
            best[node] = best[rc]

    def insert(root: int, pos: int, delta: int) -> int:
        """在 root 的树上给叶子 pos 加 delta（差分点），缺路径就动态开点。"""
        if not root:
            left.append(0)
            right.append(0)
            mx.append(0)
            best.append(0)
            root = len(mx) - 1
        cur, l, r = root, 0, K - 1
        path = [cur]  # 自顶向下记录路径，最后统一回推 (mx, best)
        while l < r:
            mid = (l + r) >> 1
            if pos <= mid:
                nxt = left[cur]
                if not nxt:
                    left.append(0)
                    right.append(0)
                    mx.append(0)
                    best.append(0)
                    nxt = len(mx) - 1
                    left[cur] = nxt
                r = mid
            else:
                nxt = right[cur]
                if not nxt:
                    left.append(0)
                    right.append(0)
                    mx.append(0)
                    best.append(0)
                    nxt = len(mx) - 1
                    right[cur] = nxt
                l = mid + 1
            cur = nxt
            path.append(cur)
        mx[cur] += delta  # 到达叶子：叶子上的计数本身就是它的 mx
        best[cur] = l
        for node in reversed(path[:-1]):  # 只回推内部节点，叶子的 mx 刚刚手工赋值
            pull(node)
        return root

    def merge(a: int, b: int) -> int:
        """把线段树 b 破坏式并入 a，返回新根；两树同区间，叶子性一致。"""
        if not a or not b:
            return a | b
        if not left[a] and not right[a]:  # a 是叶子 <=> 区间长 1，b 同区间也必是叶子
            mx[a] += mx[b]  # 叶子计数相加，种类不变
            return a
        left[a] = merge(left[a], left[b])
        right[a] = merge(right[a], right[b])
        pull(a)
        return a

    def mode_kind(root: int) -> int:
        """返回树中计数最大的物品种类；并列取编号最小，空树返回 0。"""
        return kinds[best[root]] if mx[root] > 0 else 0

    # 树上差分：路径 (x,y) 拆成 x+1、y+1、lca-1、lca父-1
    roots = [0] * (n + 1)
    for i in range(m):
        x, y, kind = qx[i], qy[i], rank[qz[i]]
        l = lca(x, y, depth, up)
        roots[x] = insert(roots[x], kind, 1)
        roots[y] = insert(roots[y], kind, 1)
        roots[l] = insert(roots[l], kind, -1)
        if parent[l]:
            roots[parent[l]] = insert(roots[parent[l]], kind, -1)

    # 逆 BFS 序：u 的树已含全部子树差分时先取答案，再并入父节点
    ans = [0] * (n + 1)
    for u in reversed(order):
        ans[u] = mode_kind(roots[u])
        if parent[u]:
            roots[parent[u]] = merge(roots[parent[u]], roots[u])

    sys.stdout.write('\n'.join(map(str, ans[1:])) + '\n')


if __name__ == "__main__":
    solve()

复杂度

时间： $O((n + m)\log n)$ 。LCA 倍增 $O((n+m)\log n)$ ；差分点插入 $O(m\log)$ ；线段树合并总摊还 $O(m \log)$ ；答案查询 $O(1)$ /点。
空间： $O(m \log)$ 个线段树节点（约 $m \cdot 17 \cdot 2$ 级别）+ 倍增表 $O(n \log n)$ ，在 $n = m = 10^5$ 下约几十 MB，可以接受。

总结

树上"路径批量加减、最后逐点查询"先差分到点上，再子树汇总，是固定套路。
"每点维护多种类计数、要众数"用权值线段树 + 线段树合并，空间从 $O(n \cdot z)$ 压到 $O(m \log)$ 。
众数查询不能依赖区间和，线段树节点必须显式维护 (区间最大计数, 取到最大值的叶子) 二元组——这是本题最隐蔽的错误来源。
合并要求两棵树区间结构一致，所以叶子总数要取 $\max(\text{种类数}, \lceil \log_2 n \rceil)$ 而不是种类数。

目录

形式化题目

直接正解

思路

代码

复杂度

总结