【学习记录】点分治

KSCD_ · 2025-05-19 21:00:58 · 个人记录

点分治之前就学过，最近机房有人让我帮调，曹神又给了道好题，自己又学了点分树，因此简单记录一下。

点分治即每次找到树的重心，并以其为中心分治，处理跨过中心的所有路径，再递归下去处理不经过中心的子树内路径。处理方式为枚举其子树，先处理该子树与之前子树之间的路径，再将该子树内的点记录下来以便之后查询。由于以重心为根时，其子树大小不超过 \frac{siz}2，因此每个节点只会被处理 O(\log n) 次，总复杂度为 O(n\log n)。思想大概就是这样，下面是例题。

P3806 【模板】点分治 1

题意

给定一棵树，边有边权，q 次询问树上是否存在长为 k 的路径，n\le10^4,q\le 100,k\le 10^7。

题解

板题，直接点分治，开桶记录目前是否存在与分治中心距离为 i 的路径，每次处理时枚举所有询问更新答案。需要注意处理完某个中心后不能清空整个桶，而是只单点清空所用到的，具体做法为另开数组记录所有 d，最后遍历该数组清空，这也是大部分点分治题保证复杂度的关键。时间复杂度 O(qn\log n)，空间复杂度 O(n+k)。

25.02-MX-D1T2 毒药

题意

给定一棵树，点有点权 a_i，求满足 a_x\oplus a_y\le \bigoplus_{i\in Path(x,y)} a_i 的二元组 (x,y) 个数。n\le2\times 10^5,a_i\le 2^{60}。

题解

记 d_i 表示 i 到根的路径异或和，则原条件转化为 a_x\oplus a_y\le d_x\oplus d_y\oplus a_{LCA(x,y)}。则容易想到枚举 LCA，统计不同子树之间点对的贡献。然而这样遍历的总次数没有保证，所以使用点分治，上式中 d 也变成点到分治中心的路径异或和。则问题转化为动态维护集合 S，集合元素为 (a,d) 二元组，多次询问 (a_x,d_x)，查询集合 S 中有多少 (a_y,d_y) 满足 a_x\oplus a_y\le d_x\oplus d_y\oplus a_{rt}。

发现只有令含 x 项和含 y 项分别在同侧，才能快速维护数量。但小于号没有交换律，所以先变不等号并移项，得到 a_x\oplus d_x\oplus a_{rt}\ne a_y\oplus d_y，然后按照 a\oplus d 分类后枚举 LCP 长度，分讨不同的最高位，最后加上相等的贡献即可。实现只需开一棵以 a\oplus d 为键值的 Trie 树，每个点记录子树内 a 该位为 0 或 1 的个数，可通过 a\oplus d 的情况得到 d 该位的值。查询时从根到对应叶子遍历一条链，处理链上节点的兄弟节点即可。

本题点分治部分仅有基本应用，在计算贡献时用到了 Trie 树，这里清空只需要清掉开的所有点即可。可能没有提交通道，只有计算贡献部分的原题 P7502，之后有时间可能会造造数据。

P10421 [蓝桥杯 2023 国 A] 树上的路径

题意

给定一棵树，求树上所有长度在 [L,R] 内的路径长度和，长度为边数。n\le 10^6。

题解

先点分治，考虑如何统计路径长度和。若枚举到 i 点，则之前子树内的 j 需满足 d_i+d_j\in [L,R]，才能产生 d_i+d_j 的贡献。即答案要加上 \sum[L-d_i\le d_j\le R-d_i](d_j+d_i)，拆括号后只需要求区间内个数和 d_j 的和，开两棵树状数组即可实现，时间复杂度 O(n\log^2 n)。

但还是不够优秀，考虑求贡献时的实质，其实是钦定顺序为 p_j<p_i，在 i 处计算贡献，其中 p_x 表示 x 所在的分治中心子树。因此若先把所有子树的贡献统计下来，并从中剔除当前子树的贡献来计算，就可以降低复杂度。对于本题，可以先将所有 d_x 放入桶中并做前缀和，枚举某棵子树时对内部所有 d_x 同样处理，求值时区间查询后用总值减去子树内的值即可。

问题在于对桶做前缀和需要值域大小的复杂度，然而某子树内的 d 不会超过子树大小，因此总值需要的数组大小为 siz_u，单个子树内需要的数组大小为 siz_v，分析得总时间复杂度为 O(n\log n)，实际运行时由于有一定常数，且上个做法中的树状数组常数较小，优化后所用时间大概是上个做法的一半。优化后求贡献的代码片段：

struct nod
{
    ll s[N]; int len;
    void cle(int x)
    {
        len=x;
        for(int i=0;i<=len;i++) s[i]=0;
    }
    void add(int p,ll x) {s[p]+=x;}
    void build() {for(int i=1;i<=len;i++) s[i]+=s[i-1];}
    ll qry(int p) {return s[min(p,len)];}
}Ta[2],Tb[2];
void sol(int u)
{
    d[u]=0,Ta[0].cle(siz[u]),Tb[0].cle(siz[u]),Ta[0].add(0,2);
    for(int v:e[u]) if(!vis[v])
    {
        tt=0,dfs(v,u);
        for(int i=1;i<=tt;i++) Ta[0].add(td[i],1),Tb[0].add(td[i],td[i]);
    }
    Ta[0].build(),Tb[0].build();
    for(int v:e[u]) if(!vis[v])
    {
        tt=0,dfs(v,u),Ta[1].cle(siz[v]),Tb[1].cle(siz[v]);
        for(int i=1;i<=tt;i++) Ta[1].add(td[i],1),Tb[1].add(td[i],td[i]);
        Ta[1].build(),Tb[1].build();
        for(int i=1;i<=tt;i++)
        {
            int l=max(0,L-td[i]),r=R-td[i];
            if(l>r) continue;
            ll x=Ta[0].qry(r)-Ta[1].qry(r),y=Tb[0].qry(r)-Tb[1].qry(r);
            if(l) x-=(Ta[0].qry(l-1)-Ta[1].qry(l-1)),y-=(Tb[0].qry(l-1)-Tb[1].qry(l-1));
            res+=x*td[i]+y;
        }
    }
}

CF2101E Kia Bakes a Cake

题意

给定一棵 n 个点的树和长为 n 的 01 串 s。称长为 m 的序列 a 合法，当且仅当 a 中元素两两不同，\forall i\in[1,m],a_i\in[1,n],s_{a_i}=1，且 \forall i\in [1,m-2],2d(a_i,a_{i+1})\le d(a_{i+1},a_{i+2})，其中 d(u,v) 表示树上 u,v 间简单路径的边数。对于 x\in[1,n] 分别求 a_1=x 时，合法 a 序列的最大长度。n\le 7\times 10^4。

题解

首先看到 2d(a_i,a_{i+1})\le d(a_{i+1},a_{i+2}) 可以很自然地注意到每次路径长度至少翻倍，而路径长度不会超过 n-1，因此序列长度不会超过 O(\log n)，或许会对本题有帮助。

之后考虑使用 DP 解决该问题，注意到 DP 状态中只能记录开头或结尾元素，难以限制两两不同。然而仔细考虑 d 的限制后发现，若两次经过点 x，设第二个 x 的前缀为 y，则有 d(y,x)>d(x,p_1)+d(p_1,p_2)+\cdots+d(p_k,y)，然而 d(y,x) 是 y\to x 的唯一最短路径，不可能存在比其长度更短的，因此序列合法时不可能存在相同元素，故可以忽略该限制。

因此 DP 就是可行的了，最朴素的 DP 状态为 f_{x,i,j} 表示 a_1=x，结尾为 i 且最后一条路径长度为 j 的最长合法序列长度。然而容易想到 x 这一维并不必要，可以将最终的序列倒过来考虑，设 f_{i,j} 表示开头为 i，第一条路径长度为 j 的最长合法序列长度，通过在开头加元素来转移，状态数压缩到了 O(n^2)，但还是难以接受。

这时想起答案不会超过 O(\log n)，因此 DP 值不会超过 O(\log n)。考虑将 DP 值和状态互换，显然序列长度相同时第一条路径越长越优。因此设 f_{i,x} 表示开头为 i，长为 x 的合法序列中第一条路径的最大长度，这样状态数就变成 O(n\log n) 的了。

之后考虑转移，f_{j,x+1}\leftarrow d(i,j) 需要满足 2d(i,j)\le f_{i,x}。考虑枚举 x 进行 O(\log n) 轮转移，并使用点分治优化，即在分治中心处转移所有路径经过中心的 (i,j) 对。则 i 转移到 j 的值为 d_i+d_j，有限制 2(d_i+d_j)\le f_{i,x}，拆开得到 2d_i-f_{i,x}\le -2d_j，这里 d_x 为深度。因此以 2d-f 为下标，用树状数组记录前缀 d_i 的最大值即可进行转移。这里需要在点分治处理时正反跑两遍，总时间复杂度 O(n\log^3 n)，分别来自状态数、点分治和树状数组，在 6s 的时限下已经可以通过，代码。

考虑能否优化到 O(n\log^2n)，发现正反跑两遍的过程实际上是把 p_i\ne p_j 的限制拆成了 p_i<p_j 或 p_i>p_j，其中 p_x 表示 x 所在的分治中心子树。如果能将所有子树的信息预处理到一起，查询时快速去掉 p_j 子树内的信息并转移，就能降低复杂度。考虑把上式整个取反为 f_{i,x}-2d_i\ge 2d_j，在每个下标上维护 d 的最大值和所属子树不同的次大值，并预处理出后缀信息。由于最大值和次大值信息合并可以 O(1) 实现，整个后缀处理仍是线性的，查询时取子树外的最大值即可。

注意到查询的 d_j 不会超过 siz_u，因此把超过 2siz_u 的下标上的值均赋到 2siz_u 上即可，数组大小得到保证，总时间复杂度 O(n\log^2n)，代码。由于常数较大，实际并没有比原来快多少。事实上限制式可以整体除以 2，得到 \lfloor \frac{f_{i,x}-2d_i}2\rfloor\ge d_j，可以通过数组大小少个 2 的常数，然而也没快多少，可能是实现得比较粗糙了。

P6329 【模板】点分树 | 震波

题意

给定一棵树，点有点权，需要支持单点修改，查询距某点不超过 k 的点权和，两点间距离为边数。强制在线，n,q\le 10^5。

题解

点分树是点分治的应用之一。具体地，令分治中心以上一层分治中心为父亲，建出一棵点分树。与点分治类似，点分树的深度不会超过 O(\log n)，同时所有点的子树大小之和也是 O(n\log n) 级别的。这允许我们暴力枚举某个点到根路径上的所有点，也允许对每个点记录其子树内所有点的信息。

这时对于某两点 u,v 间的路径，我们用点分树上 LCA 代替原树 LCA 作为分界点，这样对于固定点 u，不同的分界点 x 只有 dep(u) 个，可以枚举。这时与 u 以 x 为 LCA 的节点为 x 子树中除去 s 子树的部分，s 为 x 子节点中子树内包含 u 的。因此对每个点 x，分别记录其子树内与 x 和 x 父亲间路径的情况，查询时枚举 x，并用 x 和 s 的信息处理出有效信息即可。

对于本题，有 dis_{u,v}=dis_{u,x}+dis_{x,v}，枚举 x 后要查询 dis_{x,v}\le k-dis_{u,x} 的点权和。因此在每个点上要分别记录其子树内的点与其和其父亲距离为 d 的点权和，求贡献时用 x 对应区间的和减去 s 对应区间的和即可。因此使用 2n 棵动态开点线段树分别维护区间和，修改时对其到根路径上的所有点均修改即可。

时间复杂度为 O((n+q)\log^2n)，用 O(1) LCA 求距离可去掉一个 log；空间复杂度理论上是 O(n\log^2 n) 的，因为线段树的有效下标总数为 O(n\log n)，然而这里远远不满，用 vector 动态开点可以通过。主函数代码：

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m,mx[0]=n,T[0].build(n),T[1].build(n);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++)
    {
        int u,v; cin>>u>>v;
        e[u].pb(v),e[v].pb(u);
    }
    tot=n,getrt(1,0),ra=rt,getrt(rt,0),solv(rt),dfs0(1,0),dfs1(1,1),dfs2(ra);
    for(int u=1;u<=n;u++) for(int i=id[u];i<id[u]+s[u];i++)
    {
        int v=p[i]; T[0].update(u,0,n,dis(v,u),a[v]);
        if(f[u]) T[1].update(u,0,n,dis(v,f[u]),a[v]);
    }
    while(m--)
    {
        int op,x,y; cin>>op>>x>>y,x^=last,y^=last;
        if(op)
        {
            int u=x,dt=y-a[x]; a[x]=y;
            while(u)
            {
                if(f[u]) T[1].update(u,0,n,dis(x,f[u]),dt);
                T[0].update(u,0,n,dis(x,u),dt),u=f[u];
            }
        }
        else
        {
            int u=x,lp=x; last=0;
            while(u)
            {
                int d=y-dis(u,x);
                if(d>=0)
                {
                    last+=T[0].query(u,0,n,0,d);
                    if(u!=x) last-=T[1].query(lp,0,n,0,d);
                }
                lp=u,u=f[u];
            }
            cout<<last<<'\n';
        }
    }
    return 0;
}