线段树合并 | EVA'S WONDERLAND

旅程比目的更重要。——John Muir

算法过程

所谓线段树合并就是多棵大小相同的线段树，对应节点相加组成的新线段树，多用于权值线段树。对于两个相同区间的节点和，合并的操作分为以下几类（假设统一以节点为根）：

如果和有一个为空，则返回不空的节点作为根
如果，则累加权值，将两个节点的值相加到节点上，返回节点
递归合并两个节点的左儿子和右儿子，再更新当前节点的值，最后返回节点

复杂度

合并两棵树的复杂度约等于这两棵树重合的节点数。也就是说，每次合并的复杂度不会超过较小的那棵的点数。既然如此，总复杂度就不会超过总点数，也就是。而访问到一个结点才会新开一个结点，所以空间复杂度也是。

板题

https://www.luogu.com.cn/problem/P4556

题意：给一颗树，每个结点有个计数器，每次会选择两个点和一个计数器，把路径上的点的计数器都加一，最后问每个点的哪个计数器值最大。

思考过程：首先如果每个点只有一个计数器，那很显然就是树上差分然后再求和。其次如果不是一棵树，就是一个点有很多个计数器，并且要求，可以想到用权值线段树。所以会想到给每个点开一个权值线段树，树上差分加减相应点的线段树，最后再用线段树合并进行求和操作。

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

inline int rd() {
    int x = 0; bool f = 0; char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 100007

int totnode;

struct node {int ls, rs, mx, mxp;} c[N << 6];

inline void pushup(int rt) {
    if (c[c[rt].ls].mx >= c[c[rt].rs].mx) {
        c[rt].mx = c[c[rt].ls].mx;
        c[rt].mxp = c[c[rt].ls].mxp;
    } else {
        c[rt].mx = c[c[rt].rs].mx;
        c[rt].mxp = c[c[rt].rs].mxp;
    }
}

void upd(int &rt, int l, int r, int p, int x) {
    if (!rt) rt = ++totnode;
    if (l == r) {
        c[rt].mx += x; c[rt].mxp = p; return;
    }
    int mid = (l + r) >> 1;
    p <= mid ? upd(c[rt].ls, l, mid, p, x) : upd(c[rt].rs, mid + 1, r, p, x);
    pushup(rt);
}

int merge(int rta, int rtb, int l, int r) {
    if (!rta || !rtb) return rta + rtb;
    if (l == r) {
        c[rta].mx += c[rtb].mx;
        return rta;
    }
    int mid = (l + r) >> 1;
    c[rta].ls = merge(c[rta].ls, c[rtb].ls, l, mid);
    c[rta].rs = merge(c[rta].rs, c[rtb].rs, mid + 1, r);
    pushup(rta);
    return rta;
}

int rot[N], ans[N];

vector<int> e[N];

int dep[N], f[N], mxson[N], sz[N], top[N];

void dfs1(int u, int d) {
    dep[u] = d;
    sz[u] = 1;
    int mxid = 0;
    for (auto v : e[u])
        if (!f[v]) {
            f[v] = u; dfs1(v, d + 1); sz[u] += sz[v];
            if (sz[v] > sz[mxid]) mxid = v;
        }
    mxson[u] = mxid;
}

void dfs2(int u, int t) {
    top[u] = t;
    if (mxson[u]) dfs2(mxson[u], t);
    for (auto v : e[u])
        if (!top[v]) dfs2(v, v);
}

inline int lca(int u, int v) {
    while (top[u] != top[v])
        dep[top[u]] > dep[top[v]] ? u = f[top[u]] : v = f[top[v]];
    return dep[u] > dep[v] ? v : u;
}

void dfs(int u, int fa) {
    for (auto v : e[u])
        if (v != fa) {
            dfs(v, u);
            rot[u] = merge(rot[u], rot[v], 1, 100000);
        }
    ans[u] = c[rot[u]].mx ? c[rot[u]].mxp : 0;
}

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i < n; ++i) {
        int u = rd(), v = rd();
        e[u].pb(v); e[v].pb(u);
    }
    f[1] = 1; dfs1(1, 1); dfs2(1, 1);
    for (int i = 1; i <= m; ++i) {
        int x = rd(), y = rd(), z = rd();
        int anc = lca(x, y);
        // printf("%d %d %d\n", x, y, anc);
        upd(rot[x], 1, 100000, z, 1);
        upd(rot[y], 1, 100000, z, 1);
        upd(rot[anc], 1, 100000, z, -1);
        if (f[anc] != anc) upd(rot[f[anc]], 1, 100000, z, -1);
    }
    dfs(1, 1);
    for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    return 0;
}

例题1

https://www.luogu.com.cn/problem/P3224