题面

深绘里一直很讨厌雨天。

灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。

虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。

无奈的深绘里和村民们只好等待救济粮来维生。

不过救济粮的发放方式很特别。

有 n 个点，形成一个树状结构。

有 m 次发放操作，每次选择两个点 x,y，对 x 到 y 的路径上（包括 x,y）的每个点发放一袋 z 类型的物品。

求完成所有发放操作后，每个点存放最多的是哪种类型的物品。

输入格式

第一行两个正整数n,m，含义如题目所示。

接下来n-1行，每行两个数(a,b)，表示(a,b)间有一条边。

再接下来m行，每行三个数(x,y,z)，含义如题目所示。

输出格式

共n行，第i行一个整数，表示第i座房屋里存放的最多的是哪种救济粮，如果有多种救济粮存放次数一样，输出编号最小的。

如果某座房屋里没有救济粮，则对应一行输出0。

数据范围

1≤n,m≤100000,
1≤z≤10^9

输入样例：

5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3

输出样例：

2
3
3
0
2

题解

需要掌握 树上LCA 和 动态开点线段树

思想 差分, 离散化

根据题意明显是 区间操作, 对于树, 那么就是树上差分 和 树剖 了

对于 (x, y) 增加 z, 根据差分, 思考发现, val[x][z], val[y][z], –val[lca(x, y)][z], –val[lca(x, y)的父节点][z], 可以在树上线性跑出 每个节点 z 的数量

而 z 异常的大, 1e9, 而 m 只有1e5, 明显需要离散化, 降低 z 的范围

就算如此 对于每个节点 跑出 每个z的数量也是 爆炸的

我们就要想到 log 级别的方法, 那就线段树了, 然而肯定会爆内存, 所以要动态开点

对于节点数, 4 * m * log2(z(离散化)), 每个节点占 12字节, 在加上乱七八糟的lca和存输入的数组, 内存也不会太紧张(你要是节点东西多了, 会爆, 还是有点卡内存的)

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

const int N = 1e5 + 5;

struct STFrom {
    int f[N][20], dep[N], lg[N], t;//N为节点的数量
    vector<int>* h;
    void init(int n, vector<int>* H) {
        t = log2(n - 1) + 1; h = H; lg[0] = -1;
        rep(i, 1, n) dep[i] = 0, lg[i] = lg[i >> 1] + 1;
    }
    void bfs(int s) {
        queue<int> q; q.push(s); dep[s] = 1;
        rep(i, 0, t) f[s][i] = 0;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (auto& y : h[x]) {
                if (dep[y]) continue;
                dep[y] = dep[x] + 1; f[y][0] = x; q.push(y);
                for (int j = 1; j <= t; ++j) f[y][j] = f[f[y][j - 1]][j - 1];
            }
        }
    }
    int lca(int x, int y) {
        if (dep[x] > dep[y]) swap(x, y);
        for (int k = dep[y] - dep[x], i = lg[k]; ~i; --i) if (k >> i & 1) y = f[y][i];
        if (x == y) return x;
        per(i, lg[dep[y]], 0) if (f[x][i] ^ f[y][i]) x = f[x][i], y = f[y][i];
        return f[x][0];
    }
    int dist(int x, int y) { return dep[x] + dep[y] - (dep[lca(x, y)] << 1); }
} ST;

struct BIT {
    struct node { int l, r, val, mx; } tr[70 * N];
    int rt[N], tot;
    void push_up(int rt) {
        if (tr[tr[rt].l].mx >= tr[tr[rt].r].mx) tr[rt].mx = tr[tr[rt].l].mx, tr[rt].val = tr[tr[rt].l].val;
        else tr[rt].mx = tr[tr[rt].r].mx, tr[rt].val = tr[tr[rt].r].val;
    }
    void change(int& p, int l, int r, int d, int k) {
        if (!p) p = ++tot;
        if (l == r) { tr[p].val = l, tr[p].mx += k; return; }
        int mid = l + r >> 1;
        if (d <= mid) change(tr[p].l, l, mid, d, k);
        else change(tr[p].r, mid + 1, r, d, k);
        push_up(p);
    }
    void merge(int& x, int y, int l, int r) {
        if (!x) { x = y; return; }
        if (!y) return;
        if (l == r) { tr[x].mx += tr[y].mx; return; }
        int mid = l + r >> 1;
        merge(tr[x].l, tr[y].l, l, mid); merge(tr[x].r, tr[y].r, mid + 1, r);
        push_up(x);
    }
    int ask(int x) { return tr[x].val; }
} bit;

int n, m, ans[N];
int x[N], y[N], z[N], w[N];
vector<int> h[N];

void dfs(int x, int fa) {
    for (auto& y : h[x]) if (y != fa) {
        dfs(y, x);
        bit.merge(bit.rt[x], bit.rt[y], 1, 1e5);
    }
    ans[x] = bit.ask(bit.rt[x]);
}

int main() {
    IOS; cin >> n >> m;
    rep(i, 2, n) {
        int u, v; cin >> u >> v;
        h[u].push_back(v); h[v].push_back(u);
    }
    ST.init(n, h); ST.bfs(1);
    rep(i, 1, m) cin >> x[i] >> y[i] >> w[i], z[i] = ST.lca(x[i], y[i]);
    rep(i, 1, m) {
        bit.change(bit.rt[x[i]], 1, 1e5, w[i], 1);
        bit.change(bit.rt[y[i]], 1, 1e5, w[i], 1);
        bit.change(bit.rt[z[i]], 1, 1e5, w[i], -1);
        bit.change(bit.rt[ST.f[z[i]][0]], 1, 1e5, w[i], -1);
    }
    dfs(1, 0);
    rep(i, 1, n) cout << ans[i] << '\n';
    return 0;
}