P6329 【模板】点分树 | 震波

点分树模版题（理解题？）

• 询问距离$x$点距离不超过$k$的点的价值总和

• 把$x$点的价值变成$y$

当我们在修改某个点的时候，是要影响到自己的父亲。如果一层一层跳，如果是一条链复杂度可想而知，但是根据点分治的子树性质，最多$\log$层。

然后用一个数据结构维护每颗子树。（每个点最多出现在所有子树里，那么需要的数据结构容量也是$n\log n$级别。

此题考虑用线段树维护即可

• 需要注意对于统计父亲结点的维护的结构时，可能会重复计算儿子，那么$tree2[u]$维护的是，在点分树下$father[u]$往$u$这个方向,深度的价值和。统计时根据情况剪掉这颗子树
• 由于复杂度$O(q\log^2n)$，需要注意常数的优化。
• 根据$maxdep[u]$，动态开点线段树。
• 处理$LCA$，使用$ST$表法
• 点分治不使用“假算法”，也方便统计。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 2e5 + 10;
const int mod = 1e9 + 7;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
struct Segment
{
    int ls[N << 7], rs[N << 7], sum[N << 7];
    int scnt;

    int tr1[N], tr2[N];
    Segment() { scnt = 0; }
    void update(int &pos, int k, int val, int l, int r)
    {
        if (!pos)
            pos = ++scnt;
        sum[pos] += val;
        if (l == r)
        {

            return;
        }
        int mid = l + r >> 1;
        if (k <= mid)
            update(ls[pos], k, val, l, mid);
        else
            update(rs[pos], k, val, mid + 1, r);
    }

    int query(int pos, int ql, int qr, int l, int r)
    {

        if (!pos)
            return 0;
        if (ql <= l && r <= qr)
        {
            return sum[pos];
        }

        int mid = l + r >> 1, ans = 0;
        if (ql <= mid)
            ans += query(ls[pos], ql, qr, l, mid);
        if (qr > mid)
            ans += query(rs[pos], ql, qr, mid + 1, r);
        return ans;
    }
} T;
vector<int> g[N];

int st[N][20], dfn[N], dep[N], tot, lg2[N];
void lcadfs(int x, int fa, int d)
{
    st[++tot][0] = x;
    dep[x] = d;
    dfn[x] = tot;
    for (int to : g[x])
    {
        if (to == fa)
            continue;
        lcadfs(to, x, d + 1);
        st[++tot][0] = x;
    }
}
int lower(int u, int v)
{
    return (dep[u] < dep[v]) ? u : v;
}

void Lca_init()
{
    lcadfs(1, 0, 1);
    for (int i = 2; i <= tot; i++)
        lg2[i] = lg2[i >> 1] + 1;
    for (int l = 1; (1 << l) <= tot; l++)
    {
        for (int i = 1; i + (1 << l) - 1 <= tot; i++)
            st[i][l] = lower(st[i][l - 1], st[i + (1 << (l - 1))][l - 1]);
    }
}

int lca(int u, int v)
{
    u = dfn[u];
    v = dfn[v];
    if (u > v)
        swap(u, v);
    int i = lg2[v - u + 1], w = (1 << i);
    return lower(st[u][i], st[v - w + 1][i]);
}
int dis(int u, int v)
{
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
int siz[N], f[N], vis[N], dsiz[N];
int rt;
int father[N];
void modify(int x, int y)
{
    int now = x, fa = 0;

    while (now)
    {
        fa = father[now];

        T.update(T.tr1[now], dis(x, now), y, 0, dsiz[now]);
        if (fa)
            T.update(T.tr2[now], dis(fa, x), y, 0, dsiz[fa]); // tr2 维护是父亲=father[now],now这个子树下的权值线段树。
        now = father[now];
    }
}
int query(int x, int k)
{
    ll ans = 0;
    int now = x, last = 0;
    while (now)
    {
        //cout << now << endl;
        int d = dis(now, x);
        if (k - d >= 0)
        {
            ans += T.query(T.tr1[now], 0, min(k - d, dsiz[now]), 0, dsiz[now]);
            if (last)
                ans -= T.query(T.tr2[last], 0, min(k - d, dsiz[now]), 0, dsiz[now]);
        }

        last = now;
        now = father[now];
    }
    return ans;
}
int gcnt;
void GetRoot(int x, int fa)
{
    siz[x] = 1;

    f[x] = 0;
    for (int to : g[x])
    {
        if (to == fa || vis[to])
            continue;
        GetRoot(to, x);
        siz[x] += siz[to];
        f[x] = max(f[x], siz[to]);
    }
    f[x] = max(f[x], gcnt - siz[x]);
    if (f[x] < f[rt])
        rt = x;
}
int mx = 0;
void Getdis(int x, int fa, int d)
{
    mx = max(d, mx);
    for (int to : g[x])
    {
        if (to == fa || vis[to])
            continue;
        Getdis(to, x, d + 1);
    }
}
void solve(int x)
{
    vis[x] = 1;
    mx = 1;
    Getdis(x, 0, 1);
    dsiz[x] = mx;
    for (int to : g[x])
    {
        if (vis[to])
            continue;
        rt = 0;
        gcnt = siz[to];
        // cout << gcnt << endl;
        GetRoot(to, x);

        //cout << x << " " << to << " " << rt << endl;
        father[rt] = x;
        solve(rt);
    }
}
int n, a[N];
void work_init()
{
    Lca_init();
    rt = 0;
    f[0] = 1e9;
    gcnt = n;
    GetRoot(1, 0);

    //cout << rt << endl;
    solve(rt);

    // GetRoot(1, 0); // 获得标准Size
    for (int i = 1; i <= n; i++)
        modify(i, a[i]);
}
int main()
{
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    n = read();
    int m = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    for (int i = 1; i < n; i++)
    {
        int u = read(), v = read();
        g[u].push_back(v);
        g[v].push_back(u);
    }

    work_init();

    int pre = 0;
    for (int i = 1; i <= m; i++)
    {
        int op = read(), x = read(), y = read();
        x ^= pre, y ^= pre;
        if (op == 1)
        {
            modify(x, y - a[x]);
            a[x] = y;
        }
        if (op == 0)
        {
            pre = query(x, y);
            printf("%d\n", pre);
        }
    }
}