Title Link: https://www.nowcoder.com/acm/contest/206/I

Main idea of the topic: in Chinese, you can meet ~ -, -.

Topic idea: the topic requires a chain update operation on the tree. It is very intuitive to think of using tree chain segmentation. What this problem requires is what color each node is dyed when it is dyed for the last K times. Because this k is fixed, we can use the line tree to maintain the number of times each node is updated and the maximum number of times a node in a chain is updated. When the maximum number of updates of an interval exceeds K, we go down to find a specific interval violently to update the answer. After updating the answer of a node, we set its value to negative infinity. Since each answer is only counted once, the overall complexity should be O(n*logn*logn). (because the title requires the K to the last, it's OK to update from the back to the front. It's not a big problem.)

See code for specific implementation:

#include <bits/stdc++.h>
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pb push_back
#define MP make_pair
#define lowbit(x) x&-x
#define clr(a) memset(a,0,sizeof(a))
#define _INF(a) memset(a,0x3f,sizeof(a))
#define FIN freopen("in.txt","r",stdin)
#define IOS ios::sync_with_stdio(false)
#define fuck(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int>pii;
typedef pair<ll, ll>pll;
typedef pair<double, int> pdi;
const int mod = 998244353;
const int MX = 1e5 + 7;
const int inf = 0x3f3f3f3f;

int n, m, k;
int MAX[MX << 2], add[MX << 2];
int ans[MX];
int fa[MX], dep[MX], id[MX], idx[MX], son[MX], top[MX], sz[MX], tot;
vector<int>E[MX];
void push_up(int rt) {
    MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]);
}
void push_down(int rt) {
    if (add[rt]) {
        add[rt << 1] += add[rt];
        add[rt << 1 | 1] += add[rt];
        MAX[rt << 1] += add[rt];
        MAX[rt << 1 | 1] += add[rt];
        add[rt] = 0;
    }
}
void dfs(int l, int r, int rt, int d) {
    if (MAX[rt] < k) return;
    if (l == r) {
        MAX[rt] = -inf;
        ans[idx[l]] = d;
        return;
    }
    push_down(rt);
    int m = (l + r) >> 1;
    dfs(lson, d); dfs(rson, d);
    push_up(rt);
}
void update(int L, int R, int d, int l, int r, int rt) {
    if (L <= l && r <= R) {
        MAX[rt]++; add[rt]++;
        dfs(l, r, rt, d);
        return;
    }
    push_down(rt);
    int m = (l + r) >> 1;
    if (L <= m) update(L, R, d, lson);
    if (R > m) update(L, R, d, rson);
    push_up(rt);
}
void dfs1(int u) {
    sz[u] = 1; son[u] = 0;
    for (auto v : E[u]) {
        if (v == fa[u]) continue;
        fa[v] = u; dep[v] = dep[u] + 1;
        dfs1(v);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int tp) {
    id[u] = ++tot; idx[tot] = u;
    top[u] = tp;
    if (son[u]) dfs2(son[u], tp);
    for (auto v : E[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
void pre_solve() {
    dfs1(1);
    dfs2(1, 1);
}
void Update(int u, int v, int d) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        update(id[top[u]], id[u], d, 1, n, 1);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    update(id[u], id[v], d, 1, n, 1);
}
struct Que {
    int u, v, c;
} q[MX];

int main() {
    FIN;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        E[u].pb(v); E[v].pb(u);
    }
    pre_solve();
    for (int i = 1; i <= m; i++) scanf("%d%d%d", &q[i].u, &q[i].v, &q[i].c);
    for (int i = m; i >= 1; i--) Update(q[i].u, q[i].v, q[i].c);
    for (int i = 1; i <= n; i++)
        printf("%d%c", ans[i], i == n ? '\n' : ' ');
    return 0;
}