python/TangDou/AcWing/P4556_0 copy.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = N << 1, R = 1e5;

struct Node {
    int l, r;
    int max, pos; // max 表示物品最大值，pos 表示物品最大值对应的类型离散化后的编号
} tr[N * 4 * 17]; //为啥开这么大的空间？？

int root[N], cnt; //记录每个节点对应的线段树的根节点的下标

struct Query {
    int x, y, z;
} query[N]; //记录所有查询

int n, m;
int h[N], e[M], ne[M], idx; //邻接表
int res[N];                 //记录每个节点的答案

void add(int a, int b) { //添加边
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

#pragma region 求LCA的倍增模板
int depth[N], f[N][17]; // dep[i] 表示节点 i 的深度，fa[i][j] 表示节点 i 向上走 2^j 步到达的节点
void bfs(int t) {       //利用递推公式:f[i,j]=f[f[i,j-1],j-1]，在bfs遍历过程中，填充递推结果数组的值
    queue<int> q;
    q.push(t);
    depth[t] = 1; //根结点的深度是1
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (depth[j]) continue;       //如果深度为0，表示没有访问过，防止走回头路
            depth[j] = depth[u] + 1;      //更新深度
            f[j][0] = u;                  //记录 j的 2^0 步可以跳到的节点是u
            for (int k = 1; k <= 16; k++) //利用递推式计算出距离j 2^1 ,2^2,2^3,....的是哪个节点
                f[j][k] = f[f[j][k - 1]][k - 1];
            q.push(j); //利用j继续扩展
        }
    }
}
//求a和b的最近公共祖先
int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b); //保证a在下，b在上
    for (int k = 16; k >= 0; k--)        //向上跳到b节点的同一层
        if (depth[f[a][k]] >= depth[b])
            a = f[a][k];
    if (a == b) return a; //都是一个节点了，返回谁都是一样的
    //开始一起向上跳
    for (int k = 16; k >= 0; k--)
        if (f[a][k] != f[b][k])
            a = f[a][k], b = f[b][k];
    //父层就是LCA
    return f[a][0];
}

#pragma endregion

void pushup(int u) { //用子节点信息更新父节点信息
    tr[u].max = max(tr[tr[u].l].max, tr[tr[u].r].max);
    //如果多个物品数量相同，优先记录最靠左的物品编号
    tr[u].pos = tr[tr[u].l].max >= tr[tr[u].r].max ? tr[tr[u].l].pos : tr[tr[u].r].pos;
}

void insert(int u, int l, int r, int x, int z) { //将 x 类型 + v
    if (l == r) {                                //找到指定类型
        tr[u].max += z;                          //修改物品个数
        tr[u].pos = tr[u].max ? l : 0;           //如果物品还有，保存下标，如果物品为空，为 0
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {                    //递归左区间
        if (!tr[u].l) tr[u].l = ++cnt; //如果左子节点不存在，动态开点
        insert(tr[u].l, l, mid, x, z);
    } else {                           //递归右区间
        if (!tr[u].r) tr[u].r = ++cnt; //如果右子节点不存在，动态开点
        insert(tr[u].r, mid + 1, r, x, z);
    }
    pushup(u); //用子节点信息更新父节点信息
}

//线段树合并
int merge(int u, int v, int l, int r) {
    if (!u) return v;           //如果 u 不存在，直接返回 v
    if (!v) return u;           //如果 v 不存在，直接返回 u
    if (l == r) {               //如果是单独一个节点
        tr[u].max += tr[v].max; //节点合并
        tr[u].pos = tr[u].max ? l : 0;
        return u;
    }
    int mid = (l + r) >> 1;
    tr[u].l = merge(tr[u].l, tr[v].l, l, mid);     //合并左子节点
    tr[u].r = merge(tr[u].r, tr[v].r, mid + 1, r); //合并右子节点
    pushup(u);                                     //用子节点信息更新父节点信息
    return u;
}

// dfs求以每个节点为根节点的子树和
void dfs(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (depth[j] <= depth[u]) continue;      //只能往下走
        dfs(j);                                  //搜索子节点
        root[u] = merge(root[u], root[j], 1, R); //合并
    }
    res[u] = tr[root[u]].pos; //记录当前节点的答案(子树和)
}

int main() {
    // OJ的环境不使用文件输入输出
#ifndef ONLINE_JUDGE
    freopen("P4556.out", "w", stdout);
    freopen("P4556.in", "r", stdin);
#endif
    //优化读入
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    memset(h, -1, sizeof h); //初始化邻接表
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a); //无向边
    }

    bfs(1); //预处理 depth[], f[][],下面要计算LCA，这个是基础数据

    //为每个节点开一个动态开点的线段树
    for (int i = 1; i <= n; i++) root[i] = ++cnt;

    for (int i = 0; i < m; i++)
        cin >> query[i].x >> query[i].y >> query[i].z; //从x到y的区间，发一个z类型的物品

    //树上差分
    for (int i = 0; i < m; i++) {
        int x = query[i].x, y = query[i].y, z = query[i].z;
        int p = lca(x, y);                                 //求出x,y的最近公共祖先
        insert(root[x], 1, R, z, 1);                       // c[x][z] + 1
        insert(root[y], 1, R, z, 1);                       // c[y][z] + 1
        insert(root[p], 1, R, z, -1);                      // c[lca(x, y)][z] - 1
        if (f[p][0]) insert(root[f[p][0]], 1, R, z, -1);   // c[fa(lca(x, y))][z] - 1
    }

    //求子树和+线段树合并
    dfs(1);

    for (int i = 1; i <= n; i++)
        printf("%d\n", res[i]);

    return 0;
}