题解 ： https://xiaoxiaoh.blog.csdn.net/article/details/104270515

一、内容

题目背景

深绘里一直很讨厌雨天。

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

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

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

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

题目描述

首先村落里的一共有 nnn 座房屋，并形成一个树状结构。然后救济粮分 mmm 次发放，每次选择两个房屋 (x, y)(x,~y)(x, y)，然后对于 xxx 到 yyy 的路径上(含 xxx 和 yyy)每座房子里发放一袋 zzz 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。
输入格式

输入的第一行是两个用空格隔开的正整数，分别代表房屋的个数 nnn 和救济粮发放的次数 mmm。

第 222 到 第 nnn 行，每行有两个用空格隔开的整数 a, ba,~ba, b，代表存在一条连接房屋 aaa 和 bbb 的边。

第 (n+1)(n + 1)(n+1) 到第 (n+m)(n + m)(n+m) 行，每行有三个用空格隔开的整数 x, y, zx,~y,~zx, y, z，代表一次救济粮的发放是从 xxx 到 yyy 路径上的每栋房子发放了一袋 zzz 类型的救济粮。
输出格式

输出 nnn 行，每行一个整数，第 iii 行的整数代表 iii 号房屋存放最多的救济粮的种类，如果有多种救济粮都是存放最多的，输出种类编号最小的一种。

如果某座房屋没有救济粮，则输出 000。

输入 #1

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

输出 #1

2
3
3
0
2

二、思路

• 前缀知识 ： 动态开点 +线段树合并
• 首先我们每个点都有m类救济粮，统计最大的救济粮个数的种类。 我们可以每个点都创建一个线段树。里面保存1~m类救济粮的最大值。

• 当对u—>v 的路径进行添加救济粮时，我们可以利用树上差分

  • 每次对u的线段树的z类进行加1， 对v的线段树的z类救济粮个数加1， 对lca的z类救济粮个数-1， 对lca的父节点救济粮个数再-1。 这样对u–>v的每个救济粮个数进行差分。

• 最后dfs的时候，只需要将2个点的线段树进行合并 。 这样里面的每类的最大就合并到一个点里面去了。
  

三、代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
struct Node {
    int lc, rc, mx, id; //mx保存最大值 id保存其编号 
} tr[N * 80];
struct E {int v, next;} e[N << 1];
int n, m, u[N], v[N], z[N], idz[N], cntz, lg, len, cnt, h[N], f[N][18], dep[N], rt[N], ans[N]; //cnt是动态开点的个数 rt代表每个节点的线段树根节点编号 
void add(int u, int v) {e[++len].v = v; e[len].next = h[u]; h[u] = len;}
void bfs() {
    dep[1] = 1; queue<int> q; q.push(1); 
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int j = h[u]; j; j = e[j].next) {
            int v = e[j].v;
            if (dep[v]) continue;
            dep[v] = dep[u] + 1;
            q.push(v); f[v][0] = u;
            for (int k = 1; k <= lg; k++) f[v][k] = f[f[v][k - 1]][k - 1];
        }
    }
}
int LCA(int x, int y) {
    if (dep[y] > dep[x]) swap(x, y);
    for (int k = lg; k >= 0; k--) {
        if (dep[f[x][k]] >= dep[y]) x = f[x][k];
    }
    if (x == y) return x;
    for (int k = lg; k >= 0; k--) {
        if (f[x][k] != f[y][k]) x = f[x][k], y = f[y][k];
    }
    return f[x][0];
}
void pushup(int id) {
    int lc = tr[id].lc, rc = tr[id].rc;
    //左边区间的编号肯定是小于右边的  所以当救济相等时存储左边的编号 
    if (tr[lc].mx >= tr[rc].mx) tr[id].mx = tr[lc].mx, tr[id].id = tr[lc].id;
    else tr[id].mx = tr[rc].mx, tr[id].id = tr[rc].id; 
}
void update(int &id, int l, int r, int x, int c) {
    if (!id) id = ++cnt; //进行动态建点
    if (l == r) {
        tr[id].mx += c; tr[id].id = l;
        return;
    } 
    int mid = (l + r) >> 1;
    if (x <= mid) update(tr[id].lc, l, mid, x, c);
    else update(tr[id].rc, mid + 1, r, x, c);
    pushup(id);
}
int merge(int p, int q, int l, int r) {
    if (!p) return q; if (!q) return p;
    if (l == r) {
        tr[p].mx += tr[q].mx;
        return p;
    }
    int mid = (l + r) >> 1;
    tr[p].lc = merge(tr[p].lc, tr[q].lc, l, mid);
    tr[p].rc = merge(tr[p].rc, tr[q].rc, mid + 1, r);
    pushup(p);
    return p;
}
void dfs(int u, int fa) {
    for (int j = h[u]; j; j = e[j].next) {
        int v = e[j].v;
        if (v == fa) continue;
        dfs(v, u);
        rt[u] = merge(rt[u], rt[v], 1, cntz);
    }
    ans[u] = tr[rt[u]].mx == 0 ? 0 : tr[rt[u]].id;
}
int main() {
    scanf("%d%d", &n, &m);
    lg = int(log(n) / log(2)) + 1;
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &u[0], &v[0]);
        add(u[0], v[0]); add(v[0], u[0]);
    }   
    bfs();
    for (int i = 1; i <= m; i++) { scanf("%d%d%d", &u[i], &v[i], &z[i]); idz[i] = z[i];}
    //对z进行离散化
    sort(idz + 1, idz + 1 + m);
    cntz = unique(idz + 1, idz + 1 + m) - idz - 1;
    for (int i = 1; i <= m; i++) {
        int lca = LCA(u[i], v[i]);
        int zt = lower_bound(idz + 1, idz + 1 + cntz, z[i]) - idz;
        update(rt[u[i]], 1, cntz, zt, 1);
        update(rt[v[i]], 1, cntz, zt, 1);
        update(rt[lca], 1, cntz, zt, -1);
        update(rt[f[lca][0]], 1, cntz, zt, -1);     
    } 
    dfs(1, 0);
    for (int i = 1; i <= n; i++) printf("%d\n", idz[ans[i]]);
    return 0;
}