4556

compaq · 2024-12-22 11:26:27 · 算法·理论

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, ans[N];
vector<int>g[N];
int fa[N][20], dep[N];
int root[N], tot;
int ls[N * 50], rs[N * 50], sum[N * 50], typ[N * 50];

// sum[] 某种类型的数量
// tpy[] 最多的那种类型 
void dfs1(int x, int f){// 预处理每个节点的深度，祖先结点 
    dep[x] = dep[f] + 1;
    fa[x][0] = f;

    for(int i = 1; (1 << i) <= dep[x]; i++) 
        fa[x][i] = fa[fa[x][i - 1]][i - 1];

    for(auto y : g[x]){
        if(y == f) continue;
        dfs1(y, x);
    }   
}

int LCA(int x, int y){
    if(dep[x] < dep[y]) swap(x, y);

    for(int i = 19; i >= 0; i--){
        if(dep[x] - dep[y] >= (1 << i))
            x = fa[x][i];
    }

    if(x == y) return x;

    for(int i = 19; i >= 0; i--){
        if(fa[x][i] != fa[y][i]){
            x = fa[x][i];
            y = fa[y][i];
        }
    }

    return fa[x][0];
}

void pushup(int u){
    if(sum[ls[u]] >= sum[rs[u]])
        sum[u] = sum[ls[u]], typ[u] = typ[ls[u]];
    else
        sum[u] = sum[rs[u]], typ[u] = typ[rs[u]];
}

int update(int rt, int pl, int pr, int z, int k){ // 返回节点编号 rt 
    if(rt == 0)
        rt = ++tot; // 动态建树 

    if(pl == pr){ // 叶子节点 
        sum[rt] += k; 
        typ[rt] = z;
        return rt; 
    }

    int mid = (pl + pr) / 2;
    if(z <= mid)
        ls[rt] = update(ls[rt], pl, mid, z, k); 
    else
        rs[rt] = update(rs[rt], mid + 1, pr, z, k);

    pushup(rt);

    return rt; // 返回普通节点的编号 
}

int merge(int x, int y, int pl, int pr){ // 将y出发的线段合并到x的线段当中 
    if(x == 0 || y == 0)  return x + y;

    if(pl == pr){
        sum[x] += sum[y];
        return x;   
    }

    int mid = (pl + pr) / 2;
    ls[x] = merge(ls[x], ls[y], pl, mid);
    rs[x] = merge(rs[x], rs[y], mid + 1, pr);

    pushup(x);
    return x; // 普通节点编号 
}

void dfs2(int x, int f){
    for(auto y : g[x]){
        if(y == f) continue;
        dfs2(y, x);
        root[x] = merge(root[x], root[y], 1, N);
    }
    ans[x] = sum[root[x]] ? typ[root[x]] : 0;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        g[x].push_back(y); g[y].push_back(x);
    }

    dfs1(1, 0);

    for(int i = 1; i <= m; i++){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        root[x] = update(root[x], 1, N, z, 1);
        root[y] = update(root[y], 1, N, z, 1);
        int lca = LCA(x, y), flca = fa[lca][0];
        root[lca] = update(root[lca], 1, N, z, -1);
        root[flca] = update(root[flca], 1, N, z, -1); 
    }

    dfs2(1, 0);

    for(int i = 1; i <= n; i++)
        printf("%d\n", ans[i]);
    return 0;
}