树剖求lca

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define pii pair<int,int>
constexpr int Mod = 998244353;
constexpr int N = 5e6 + 10;
constexpr int qwq = 1e5;
int rt[N];
int maxn[N], id[N];
int ls[N], rs[N];
int tot;
void pushup(int pos) {
    if(maxn[ls[pos]] > maxn[rs[pos]]) {
        maxn[pos] = maxn[ls[pos]];
        id[pos] = id[ls[pos]];
    } else if(maxn[ls[pos]] == maxn[rs[pos]]) {
        maxn[pos] = maxn[ls[pos]];
        id[pos] = max(id[ls[pos]], id[rs[pos]]);
    } else {
        maxn[pos] = maxn[rs[pos]];
        id[pos] = id[rs[pos]];
    }
}
void change(int &pos, int l, int r, int qpos, int k) {
    if(!pos) pos = ++tot;
    if(l == r) {
        maxn[pos] += k;
        id[pos] = l;
        return;
    }
    int mid = l + r >> 1;
    if(qpos <= mid) change(ls[pos], l, mid, qpos, k);
    if(mid < qpos) change(rs[pos], mid + 1, r, qpos, k);
    pushup(pos);
}
int merge(int u, int v, int l, int r) {
    if(!u || !v) return u + v;
    if(l == r) {
        maxn[u] += maxn[v];
//    printf("%d %d %d %d %d %d\n", u, l, r, val[u], maxn[u], id[u]);
//    printf("%d %d %d %d %d %d\n", v, l, r, val[v], maxn[v], id[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);
//    printf("%d %d %d %d %d %d\n", u, l, r, val[u], maxn[u], id[u]);
//    printf("%d %d %d %d %d %d\n", v, l, r, val[v], maxn[v], id[v]);
    pushup(u);
    return u;
}
vector<int>tr[N];
int depth[N], siz[N], fa[N], hson[N];
int top[N], dfn[N], dfc;
void dfs1(int x, int pre) {
    fa[x] = pre;
    siz[x] = 1;
    depth[x] = depth[pre] + 1;
    for(int y : tr[x]) {
        if(y == pre) continue;
        dfs1(y, x);
        siz[x] += siz[y];
        if(siz[hson[x]] < siz[y]) hson[x] = y;
    }
}
void dfs2(int x, int pre, int t) {
    top[x] = t;
    dfn[x] = ++dfc;
    if(hson[x]) dfs2(hson[x], x, t);
    for(int y : tr[x]) {
        if(y == pre || y == hson[x]) continue;
        dfs2(y, x, y);
    }
}
int lca(int x, int y) {
    while(top[x] != top[y]) {
        if(depth[top[x]] < depth[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    if(depth[x] < depth[y]) return x;
    else return y;
}
int ans[N];
void dfs(int x, int pre) {
    for(int y : tr[x]) {
        if(y == pre) continue;
        dfs(y, x);
//        printf("[%d %d]:\n",x,y);
        rt[x] = merge(rt[x], rt[y], 1, qwq);
    }
    ans[x] = id[rt[x]];
}
int n, m;
signed main() {
    cin >> n >> m;
    for(int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        tr[x].push_back(y);
        tr[y].push_back(x);
    }
    dfs1(1, 0);
    dfs2(1, 0, 1);
    while(m--) {
        int x, y, k;
        cin >> x >> y >> k;
        change(rt[x], 1, qwq, k, 1);
        change(rt[y], 1, qwq, k, 1);
        change(rt[lca(x, y)], 1, qwq, k, -1);
        if(lca(x, y) != 1) change(rt[fa[lca(x, y)]], 1, qwq, k, -1);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; i++) cout << ans[i] << '\n';
    return 0;
}