洛谷AC链接： 洛谷ac链接

vjudge TLE链接： vjudge TLE链接

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 100010, NN = 100000;

int n, m, id;
int h[N], ne[N * 2], e[N * 2], idx;
struct Node {
    int l, r;
    int cnt; // 区间总计数
    int tmax; // 区间内单点计数最大值
} tr[N * 50];
int depth[N], fa[N][18];
int ans[N];
int root[N]; // 每一个节点对应的线段树根节点

inline void add(int a, int b) {
    ne[idx] = h[a], e[idx] = b, h[a] = idx ++;
}

// 求depth数组，fa数组
inline void bfs() {
    queue<int> q;
    q.push(1);
    for (int i = 0; i <= n; i ++) depth[i] = 0x3f3f3f3f;
    depth[0] = 0, depth[1] = 1;
    while (q.size()) {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                q.push(j);
                fa[j][0] = t;
                for (int k = 1; k <= 17; k ++) {
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
                }
            }
        }
    }
}

// 倍增求lca
inline int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 17; k >= 0; k --) {
        if (depth[fa[a][k]] >= depth[b]) a = fa[a][k];
    }
    if (a == b) return a;
    for (int k = 17; k >= 0; k --) {
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}

inline void pushup(int q) {
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    tr[q].tmax = max(tr[tr[q].l].tmax, tr[tr[q].r].tmax);
}

inline int insert() {
    int q = ++ id;
    return q;
}

void update(int &q, int l, int r, int x, int d) {
    if (!q) q = ++ id;
    if (l == r) {
        tr[q].cnt += d;
        tr[q].tmax = tr[q].cnt;
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid) update(tr[q].l, l, mid, x, d);
    if (x > mid) update(tr[q].r, mid + 1, r, x, d);
    pushup(q);
    return;
}

// 合并线段树
void merge(int &x, int y) {
    if (!x || !y) {
        x = x + y;
        return;
    }
    merge(tr[x].l, tr[y].l);
    merge(tr[x].r, tr[y].r);
    
    tr[x].cnt = tr[x].cnt + tr[y].cnt;
    if (!tr[x].l && !tr[x].r && !tr[y].l && !tr[y].r) tr[x].tmax = tr[x].cnt;
    else pushup(x);
    
    return;
}

int query(int q, int l, int r) {
    if (tr[q].tmax == 0) return 0;
    if (l == r) return r;
    int mid = l + r >> 1;
    int lmax = tr[tr[q].l].tmax, rmax = tr[tr[q].r].tmax;
    if (lmax >= rmax) return query(tr[q].l, l, mid);
    return query(tr[q].r, mid + 1, r);
}

void dfs(int u, int father) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j != father) {
            dfs(j, u);
            merge(root[u], root[j]);
        }
    }
    ans[u] = query(root[u], 1, NN);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    while (cin >> n >> m) {
        if (!n && !m) break;
        
        // 初始化
        idx = 0, id = 0;
        for (int i = 0; i <= n; i ++) h[i] = -1;
        
        for (int i = 1; i <= n - 1; i ++) {
            int a, b;
            cin >> a >> b;
            add(a, b), add(b, a);
        }
        bfs();
        
        for (int i = 1; i <= n; i ++) root[i] = insert();
    
        while (m --) {
            int a, b, c;
            cin >> a >> b >> c;
            int p = lca(a, b);
            update(root[a], 1, NN, c, 1);
            update(root[b], 1, NN, c, 1);
            update(root[p], 1, NN, c, -1);
            update(root[fa[p][0]], 1, NN, c, -1);
        }
    
        dfs(1, -1);
    
        for (int i = 1; i <= n; i ++) cout << ans[i] << endl;
        
        // 清空数组
        for (int i = 0; i <= id; i ++) tr[i].l = tr[i].r = tr[i].cnt = tr[i].tmax = 0;
    }
    
    return 0;
}