【题解】P6329 【模板】点分树 | 震波

· · 题解

upd：代码添加了注释

upd：有同学提到 \texttt{vector} 的 resize 问题，emmm文章里说的是开 \texttt{vector} 的大小应该是 子树大小 +1，但是这里要实现树状数组，所以下标从 1 开始，还要多开一位，所以应该是 resize(子树大小+2)，代码略有修改（主要是 \texttt{vector} 大小的修改）。

写篇题解纪念一下这道自己调了好久的题...

写在前面

由于太菜，花了很久才弄懂。也希望能够以此文帮助更多想要学习点分树的同学。如有问题，请在评论区指出。

关于点分治

首先，要学习点分树，首先要理解点分治的过程。

按照我的理解，点分治的过程在于：先处理当前树的答案，再选择当前树的重心，把它删掉，然后递归地处理剩下的子树。

这样做可以做到比较优秀的复杂度。

关于点分树

点分树可以看做是将整个点分治过程记录下来，将当前树的重心与上一层的树的重心连边（后者视作前者的父亲），这样就可以得到一个形态比较优秀的重构树，可以以比较优秀的复杂度解决不考虑树的形态的一类问题。

回到题目

这道题要我们动态维护对于某个点距离小于 k 的点的权值和，这就是上述的典型的与树的形态无关的一类题目。

考虑一种暴力，每次询问都用点分治暴力求解，那么我们每次都找到重心统计答案即可。

可以发现，对于多次这样的询问，都进行了找重心的操作，但这是完全重复的，所以我们只用把对于每个重心的答案记录下来并查询即可。

我们具体地来看一看这个查询操作。

在点分治的过程中，我们会有一个数组 C 来记录对于这个点其子树内的点到它的每个距离对应的答案。

这是原树，每条边边权为 1 。

这是一种重构树。（其实也有一种重构树和原树的形态完全一致，但为了以示区别，我用了这个）

那么考虑当 x=4 ， y=2 时，通过原图我们可以发现，其实就是查询节点 1 、 3 的权值和。

那我们再看看在重构树上怎么做。

从节点 4 出发，查询距离 ≤2 的答案。

回忆一下点分治的做法，从整棵树的重心一步步地分治到当前节点。也就是说，从现在重构树的节点一直统计到当前节点。

这个是很好做的，我们只需要记录重构树的父子关系，计算当前节点答案需要经过的点即为重构树根节点到当前节点路径上的所有点。

那么我们再来考虑如何统计答案。

上面说到，要提出当前节点到重构树根节点的路径上的点，实际上就是从当前节点一直跳父亲，跳到根为止。

最开始在 x 的时候，直接将 x 子树的节点对 x 的贡献加入答案即可。再考虑在往上爬的过程中（设当前节点为 u ，与 x 的距离为 dis ），我们需要计算的是在 u 子树内但不在 x 子树内的节点对 x 的贡献，也就是在 u 子树但不在 x 子树的节点中与 x 的距离 ≤y-dis 的节点的权值和。那么容斥一下可以得到，我们要求的就是与 u 子树内 u 距离 ≤y-dis 的节点权值和减去 x 子树内与 u 距离 ≤y-dis 的权值和。

容易发现，如果我们记 W_{i,j} 为 i 子树内与 i 的距离为 j 的节点权值和，那么我们每次询问的都是 W_i 的前缀和，那么我们就可以用树状数组来维护这些信息了。

注意上面要用到的信息有两个：

我们分别用 C_{0,i},C_{1,i} 表示这两个树状数组。

那么每次查询的时候只需要按照上述步骤完成即可，每次询问复杂度是 O(\log^2n) 的。注意由于 n 很大，直接暴力开数组存不下，可以用 \texttt{vector} 来存，大小为 i 的子树大小 +1 （由于距离可能为 0 ，需要将树状数组整体右移，如 C_{0,i,j} 其实表示的是 i 子树内与 i 距离为 j-1 的节点对 i 的贡献）。

对于修改操作，那么我们只需要按照上述规则，修改 C_{0,i},C_{1,i} 即可，每次修改复杂度也是 O(\log^2n) 。

于是就可以愉快地通过这道题了。

#include <bits/stdc++.h>
#define REP(u) for(int i = H[u], v; i, v = E[i].v; i = E[i].n)
using namespace std;
const int maxn = 2e5 + 111, inf = 1e9 + 7;
int N, M, tot, ans, rt, sum, minn, cnt;
int val[maxn], H[maxn], sz[maxn], fa[maxn], dep[maxn], pos[maxn], ol[maxn<<1][21], lg[maxn<<1];
//val表示该城市的价值，sz表示该点子树的大小，fa表示该点点分树上的父亲节点，dep表示该点的深度 
bool vis[maxn];
vector<int>C[2][maxn];
//C[0][i]表示i子树内节点对i的贡献
//C[1][i]表示i子树内节点对i父亲的贡献 
struct edge {
    int n, v;
}E[maxn<<1];
void add(int u, int v)
{
    E[++tot] = (edge) {H[u], v};
    H[u] = tot;
}
void dfs0(int u, int f)
{
    ol[++cnt][0] = u, pos[u] = cnt;
    REP(u) if(v ^ f) dep[v] = dep[u] + 1, dfs0(v, u), ol[++cnt][0] = u;
}
int get_min(int a, int b)
{
    return dep[a] < dep[b] ? a : b;
}
void get_ol() 
{
    for(int i = 1; i <= cnt; ++i) lg[i] = 31 - __builtin_clz(i);
    for(int t = 1; 1 << t <= cnt; ++t)
        for(int i = 1; i + (1 <<t) <= cnt; ++i)
            ol[i][t] = get_min(ol[i][t - 1], ol[i + (1 << (t - 1))][t - 1]);
}
int get_dis(int u, int v)
{
    if(pos[u] > pos[v]) swap(u, v);
    int uu = pos[u], vv = pos[v], len = vv - uu + 1;
    int lca = get_min(ol[uu][lg[len]], ol[vv - (1 << lg[len]) + 1][lg[len]]);
    return dep[u] + dep[v] - 2 * dep[lca];
}
#define lowbit(x) (x & -x)
void upd(int u, int opt, int x, int addv)
{
    x++;
    for(int i = x; i <= sz[u]; i += lowbit(i)) C[opt][u][i] += addv;
}
int qry(int u, int opt, int x)
{
    x++;
    int res = 0;
    x = min(x, sz[u]);
    for(int i = x; i; i -= lowbit(i)) res += C[opt][u][i];
    return res;
}
void find_rt(int u, int f) //找重心 
{
    sz[u] = 1;
    int res = 0;
    REP(u) if(f ^ v && !vis[v]) find_rt(v, u), sz[u] += sz[v], res = max(res, sz[v]);
    res = max(res, sum - sz[u]);
    if(res < minn) minn = res, rt = u; 
}
void dfs(int u) //建立点分树 
{
    vis[u] = 1;
    sz[u] = sum+1;
    C[0][u].resize(sz[u]+1);
    C[1][u].resize(sz[u]+1);
    REP(u) if(!vis[v]) 
    {
        sum = sz[v], rt = 0, minn = inf;
        find_rt(v, 0);
        fa[rt] = u;
        dfs(rt);
    }
}
void modify(int u, int w)
{
    for(int i = u; i; i = fa[i]) upd(i, 0, get_dis(u, i), w); 
    for(int i = u; fa[i]; i = fa[i]) upd(i, 1, get_dis(u, fa[i]), w);   
}
int main()
{
    int opt, x, y;
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= N; ++i) scanf("%d", &val[i]);
    for(int i = 1; i <  N; ++i) scanf("%d%d", &x, &y), add(x, y), add(y, x);
    dfs0(1, 0);
    get_ol();
    sum = N, minn = inf;
    find_rt(1, 0);
    dfs(rt);
    for(int i = 1; i <= N; ++i) modify(i, val[i]); 
    while(M--)
    {
        scanf("%d%d%d", &opt, &x, &y);
        x ^= ans, y ^= ans; 
        if(!opt) 
        {
            ans = 0;
            ans += qry(x, 0, y); //x子树内到其距离为y的点对x的贡献 
            for(int i = x; fa[i]; i = fa[i])
            {
                int dis = get_dis(x, fa[i]);  
                if(y >= dis) ans += qry(fa[i], 0, y - dis) - qry(i, 1, y - dis); //x子树外到其距离为y的点 
                //fa[i]子树中除x所在子树对x的贡献 即为 fa[i]子树对它的总贡献 减去 x所在子树对fa[i]的贡献 
            }
            printf("%d\n", ans);
        }
        else modify(x, y - val[x]), val[x] = y; //利用差分的办法修改其对点分树上祖先的贡献 
    }
    return 0;
}