题意
给一棵 \(n\) 个节点的无根树，共 \(m\) 次操作，每次操作是一个三元组 \((x, y, z)\)，表示路径 \((x \to y)\) 全部发一袋类型为 \(z\) 的救济粮。问最后每座房子存放最多的是哪种救济粮。
思路
看到树上路径的操作，首先考虑差分，但本题的特殊之处在于每个节点有 \(10^5\) 种不同的贡献需要维护。
朴素想法是开一个二维数组 \(val[u][i]\) 表示节点 \(u\) 有多少袋种类为 \(i\) 的救济粮，这样的话时空都是 \(O(np)\)，\(p\) 是救济粮的种类。（时间的瓶颈是在最后深搜统计答案）
考虑到我们最后只询问每个点最多的是哪种救济粮，因此过程中其实维护了很多无用的信息（硬要说有用的话，只用于了答案取 \(\max\)），这显然是非常费时的。
我们可以使用线段树合并，来快速地只维护每个节点的 \(max\) 救济粮。
本题显然是值域线段树，而且每个节点都要开一棵，差分部分 \(4\) 次打标记就换成 \(4\) 次单点修。
打完标记 dfs 合并答案就是真正的线段树合并部分。其原理就是 \(u,v\) 两个节点的线段树采用同步遍历，当移动到只有一方有点时，就直接用这个点，否则就遍历到叶子节点，把贡献统一放到 \(u\) 的线段树上。
关于空间，采用动态开点，每次打 \(4\) 个差分标记最多会创造 \(4\) 条新的长度为 \(\log n\) 的链，因此空间不超过 \(O(4mlogn)\)。
关于时间，其实是所有点对 \((u, v)\) 进行合并，复杂度为 \(O(mlogn)\)。
记得合并的时候要上传合并后该点的新编号。
实现
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long;
const int N = 1e5 + 5, maxn = 1e5;
struct node{
int v, ne;
}e[N << 1];
int first[N], ans[N], idx = 0;
int n, m;
int root[N];
void add(int x, int y){
e[++ idx] = (node){y, first[x]};
first[x] = idx;
}
struct LCA{
int dep[N], fa[N], dfn[N], rev[18][N], cnt = 0;
void add(int x, int y){
e[++ idx] = (node){y, first[x]};
first[x] = idx;
}
void dfs(int u, int f){
fa[u] = f;
dep[u] = dep[f] + 1;
dfn[u] = ++ cnt;
rev[0][cnt] = u;
for(int i = first[u]; i; i = e[i].ne){
int v = e[i].v;
if(v == f) continue;
dfs(v, u);
}
}
int cmin(int x, int y){
if(dep[x] < dep[y]) return x;
return y;
}
int getlca(int x, int y){
if(x == y) return x;
if((x = dfn[x]) > (y = dfn[y])) swap(x, y);
int t = __lg(y - x++);
return fa[cmin(rev[t][x], rev[t][y - (1 << t) + 1])];
}
void init(){
dfs(1, 0);
F(j, 1, 17) F(i, 1 , n - (1 << j) + 1) rev[j][i] = cmin(rev[j - 1][i], rev[j - 1][i + (1 << (j - 1))]);
}
}lca;
struct Segtree{
int mx[N * 50], typ[N * 50], ls[N * 50], rs[N * 50], cnt;
void pushup(int u){
if(mx[ls[u]] >= mx[rs[u]]){
mx[u] = mx[ls[u]];
typ[u] = typ[ls[u]];
}
else{
mx[u] = mx[rs[u]];
typ[u] = typ[rs[u]];
}
}
void update(int &u, int l, int r, int x, int v){
if(!u) u = ++ cnt;
if(l == r){
mx[u] += v;
typ[u] = x;
return ;
} int mid = (l + r) >> 1;
if(x <= mid) update(ls[u], l, mid, x, v);
else update(rs[u], mid + 1, r, x, v);
pushup(u);
}
int merge(int u, int v, int l, int r){
if(!u || !v) return u + v;
if(l == r){
mx[u] += mx[v];
return u;
} int mid = (l + r) >> 1;
ls[u] = merge(ls[u], ls[v], l, mid);
rs[u] = merge(rs[u], rs[v], mid + 1, r);
pushup(u);
return u;
}
void spread(int u){
for(int i = first[u]; i; i = e[i].ne){
int v = e[i].v;
if(v == lca.fa[u]) continue;
spread(v);
root[u] = merge(root[u], root[v], 1, maxn); // 一定记得更新 root[u]
}
ans[u] = mx[root[u]] ? typ[root[u]] : 0;
}
}tr;
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
F(i, 1, n - 1){
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
lca.init();
while(m --){
int x, y, z;
cin >> x >> y >> z;
int p = lca.getlca(x, y);
tr.update(root[x], 1, maxn, z, 1);
tr.update(root[y], 1, maxn, z, 1);
tr.update(root[p], 1, maxn, z, -1);
tr.update(root[lca.fa[p]], 1, maxn, z, -1);
}
tr.spread(1);
F(i, 1, n) cout << ans[i] << '\n';
return fflush(0), 0;
}