如题目所言，这就是个线段树合并的板子题。
题目大意
题目描述
首先村落里的一共有 \(n\) 座房屋，并形成一个树状结构。然后救济粮分 \(m\) 次发放，每次选择两个房屋 \((x, y)\)，然后对于 \(x\) 到 \(y\) 的路径上（含 \(x\) 和 \(y\)）每座房子里发放一袋 \(z\) 类型的救济粮。
然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。
输入格式
输入的第一行是两个用空格隔开的正整数，分别代表房屋的个数 \(n\) 和救济粮发放的次数 \(m\)。
第 \(2\) 到 第 \(n\) 行，每行有两个用空格隔开的整数 \(a, b\)，代表存在一条连接房屋 \(a\) 和 \(b\) 的边。
第 \((n + 1)\) 到第 \((n + m)\) 行，每行有三个用空格隔开的整数 \(x, y, z\)，代表一次救济粮的发放是从 \(x\) 到 \(y\) 路径上的每栋房子发放了一袋 \(z\) 类型的救济粮。
输出格式
输出 \(n\) 行，每行一个整数，第 \(i\) 行的整数代表 \(i\) 号房屋存放最多的救济粮的种类，如果有多种救济粮都是存放最多的，输出种类编号最小的一种。
如果某座房屋没有救济粮，则输出 \(0\)。
样例输入
5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3
样例输出
2
3
3
0
2
数据范围
对于 \(20\%\) 的数据，保证 \(n, m \leq 100\)。
对于 \(50\%\) 的数据，保证 \(n, m \leq 2 \times 10^3\)。
对于 \(100\%\) 测试数据，保证 \(1 \leq n, m \leq 10^5\)，\(1 \leq a,b,x,y \leq n\)，\(1 \leq z \leq 10^5\)。
大概思路
先建好图，再跑树剖（求lca），用树上点差分表示每个点上的物品的个数，再把每个点当成一个线段树进行线段树合并，将子节点合并到父节点上，求出每个点上最多的物品种类即可。
本题 \(z\) 的数据范围不是很大，如果过大则需要离散化。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int maxn(100005);
inline int read() {
int f(1), x(0);
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c & 15);
return f * x;
}
int n, m, a, b, c;
int head[maxn], nxt[maxn << 1], ver[maxn << 1], tot;
int hson[maxn], dep[maxn], fa[maxn], siz[maxn];
int dfn[maxn], rdfn[maxn], cnt, top[maxn];
int d[maxn]; // 可以理解为差分数组，但更好地理解是，d[]是一棵棵线段树
int ans[maxn];
inline void add(int x, int y) {
ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}
void dfs1(int x) {
hson[x] = -1; siz[x] = 1;
for (int i = head[x]; ~i; i = nxt[i]) {
int y = ver[i];
if (dep[y]) continue;
fa[y] = x;
dep[y] = dep[x] + 1;
dfs1(y);
siz[x] += siz[y];
if (hson[x] == -1 || siz[y] > siz[hson[x]]) hson[x] = y;
}
}
void dfs2(int x, int f) {
top[x] = f;
dfn[x] = ++cnt; rdfn[cnt] = x;
if (hson[x] == -1) return;
dfs2(hson[x], f);
for (int i = head[x]; ~i; i = nxt[i]) {
int y = ver[i];
if (y != fa[x] && y != hson[x]) dfs2(y, y);
}
}
int lca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
return x;
};
int cnt1;
struct SegmentTree {
int l, r, res, num;
// res 是种类，num 是物品个数
} t[maxn << 6]; // 权值线段树，这里开64倍
void pushup(int p) {
if (t[t[p].l].num >= t[t[p].r].num) {
t[p].num = t[t[p].l].num;
t[p].res = t[t[p].l].res;
} else {
t[p].num = t[t[p].r].num;
t[p].res = t[t[p].r].res;
}
}
int merge(int a, int b, int l, int r) {
if (!a) return b;
if (!b) return a;
if (l == r) {
t[a].num += t[b].num;
return a;
}
int mid = (l + r) >> 1;
t[a].l = merge(t[a].l, t[b].l, l, mid);
t[a].r = merge(t[a].r, t[b].r, mid + 1, r);
pushup(a);
return a;
}
int insert(int p, int l, int r, int x, int v) {
if (!p) p = ++cnt1;
if (l == r) {
t[p].num += v;
t[p].res = x;
return p;
}
int mid = (l + r) >> 1;
if (x <= mid) t[p].l = insert(t[p].l, l, mid, x, v);
else t[p].r = insert(t[p].r, mid + 1, r, x, v);
pushup(p);
return p;
}
void redfs(int x) {
for (int i = head[x]; ~i; i = nxt[i]) {
int y = ver[i];
if (dep[y] <= dep[x]) continue;
redfs(y);
d[x] = merge(d[x], d[y], 1, 100000);
}
if (t[d[x]].num) ans[x] = t[d[x]].res;
}
int main() {
memset(head, 0xff, sizeof(head));
dep[1] = 1;
n = read(), m = read();
for (int i = 1; i < n; ++i) {
a = read(), b = read();
add(a, b); add(b, a);
}
dfs1(1), dfs2(1, 1);
for (int i = 1; i <= m; ++i) {
a = read(); b = read(), c = read();
d[a] = insert(d[a], 1, 100000, c, 1);
d[b] = insert(d[b], 1, 100000, c, 1);
int t = lca(a, b);
d[t] = insert(d[t], 1, 100000, c, -1);
if (fa[t]) d[fa[t]] = insert(d[fa[t]], 1, 100000, c, -1);
}
redfs(1);
for (int i = 1; i <= n; ++i) {
printf("%d\n", ans[i]);
}
}