[图论/数据结构] 一种重链剖分的扩展

Felix72 · 2025-08-12 16:23:58 · 算法·理论

这里记录一种可以以 O(k\log^2n) 时间复杂度（单次询问），O(nk) 空间复杂度实现 d(\leq k) 级邻域加，子树加，链加，以及对应求和的重链剖分方式。

先对该树进行一次正常的重链剖分，然后对其进行两轮 DFS。

第一轮 DFS 伪代码如下：

对当前点 u 进行 BFS；
对于每个儿子 v:
  递归进入 v;

第二轮 DFS 伪代码如下：

若当前点 u 还没有 dfn 标号，则给 u 的 dfn 标号 ++idx;
递归进入重儿子;
对于其他儿子 v:
  递归进入 v;

第一轮 DFS 中提到的特殊 BFS 伪代码如下：

将起点 s 加入队列;
当队列非空:
  取出队首节点 u;
  如果 u 是其所在重链的前 k 个点之一，且 u 还没有 dfn 标号:
    给 u 的 dfn 编号 ++idx;
  若 u 到 s 的距离小于 d:
    遍历 u 的所有儿子，将它们加入队列

上面的流程实际上做了这样的事情：

我们把树上的所有点分为两类，规定每条重链上的前 k 个点为 A 类点，剩下的都是 B 类点。我们可以发现在刚才的流程中，第一轮 DFS 是在给 A 类点标号，第二轮则是在给 B 类点标号。最终的结果就是，A 类点的 dfn 形成了一个“类 BFS 序状物”，B 类点的 dfn 形成了一个“类树剖状物”，且 A 类点A 类点的 dfn 都小于 B 类点。

我们可以用这个 dfn 序以单次 O(k\log^2n) 的时间复杂度做很多种操作。以下逐一讲解：

路径修改

可以发现 B 类点的 dfn 遵循传统的树链剖分规律，因此我们可以按照经典的方式维护路径修改，并对途中每条重链的前 k 个点单点修改。

d 级邻域修改

这个问题可以转化成多次对一个点所有 r 级儿子的修改操作。因为 r \leq d \leq k，因此 r 级儿子中最多只有一个点是 B 类点，剩下的都是 A 类点，它们的 dfn 序遵循 BFS 序规律，是连续的，可以在数据结构上区间修改。处理完后再对单独的 A 类点单点修改即可。

子树修改

先对一个点的 [0, k] 级儿子做 k + 1 次上面的单层修改，然后我们可以发现，子树中剩下的节点有些是 A 类点，有些是 B 类点，但是同类点的 dfn 编号都是连续的。因此再做两次区间修改即可。

查询操作是类似的。这样，我们便得到了可以处理 k 级邻域的重链剖分。

下面是一个粗糙的实现：

/* K_crane x N_Cat */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 100010, D = 110, mod = 998244353;
int Type, n, m, d; vector < int > tr[N]; long long org[N];

int rt, idx;
struct Line {long long k, b;};
Line operator * (Line u, Line v) {return {u.k * v.k % mod, (v.k * u.b + v.b) % mod};}
struct SGT
{
    int ls, rs; Line data, tag;
    #define ls(x) tree[x].ls
    #define rs(x) tree[x].rs
    #define data(x) tree[x].data
    #define tag(x) tree[x].tag
} tree[N * 2];
inline void push_tag(int now, Line _tag)
{data(now) = data(now) * _tag, tag(now) = tag(now) * _tag;}
inline void pushdown(int now)
{
    push_tag(ls(now), tag(now));
    push_tag(rs(now), tag(now));
    tag(now) = {1, 0};
}
inline void build(int &now, int l, int r)
{
    now = ++idx;
    data(now) = tag(now) = {1, 0};
    if(l == r) return ; int mid = (l + r) >> 1;
    build(ls(now), l, mid), build(rs(now), mid + 1, r);
}
inline void modify(int now, int l, int r, int L, int R, Line dt)
{
    if(L <= l && r <= R) {push_tag(now, dt); return ;}
    pushdown(now); int mid = (l + r) >> 1;
    if(L <= mid) modify(ls(now), l, mid, L, R, dt);
    if(mid < R) modify(rs(now), mid + 1, r, L, R, dt);
}
inline Line query(int now, int l, int r, int pos)
{
    if(l == r) return data(now);
    pushdown(now); int mid = (l + r) >> 1;
    if(pos <= mid) return query(ls(now), l, mid, pos);
    else return query(rs(now), mid + 1, r, pos);
}

int dep[N], siz[N], son[N], fa[N][22], top[N], len[N];
int dfn[N], rnk[N], df_sign, id[N][D], sum[N][D], min_id[N][D], nxt[N][D];
int tpA[N][D], tpB[N][D], far_tpA[N], far_tpB[N], Aid[N][D], Bid[N][D], far_Aid[N], far_Bid[N];
inline void init_A(int pos, int prt)
{
    sum[pos][0] = 1;
    dep[pos] = dep[prt] + 1, siz[pos] = 1, fa[pos][0] = prt;
    for(int i = 1; ; ++i)
    {
        if(fa[fa[pos][i - 1]][i - 1]) fa[pos][i] = fa[fa[pos][i - 1]][i - 1];
        else break;
    }
    for(int to : tr[pos])
    {
        if(to == prt) continue;
        init_A(to, pos), siz[pos] += siz[to];
        if(siz[to] > siz[son[pos]]) son[pos] = to;
        for(int i = 1; i <= d; ++i) sum[pos][i] += sum[to][i - 1];
    }
}
queue < int > q;
inline void bfs(int st, bool spe = false)
{
    q.push(st);
    while(!q.empty())
    {
        int pos = q.front(); q.pop();
        if(dep[pos] - dep[top[pos]] <= d)
        {
            if(!dfn[pos]) dfn[pos] = ++df_sign, rnk[df_sign] = pos;
            if(!id[st][dep[pos] - dep[st]]) id[st][dep[pos] - dep[st]] = dfn[pos];
        }
        if(dep[pos] - dep[st] == d) continue;
        for(int to : tr[pos])
        {
            if(to == fa[pos][0]) continue;
            q.push(to);
        }
    }
}
inline void init_B(int pos, int belong)
{
    nxt[pos][0] = pos;
    for(int i = 1; i <= d; ++i) nxt[pos][i] = son[nxt[pos][i - 1]];
    top[pos] = belong;
    if(son[pos]) init_B(son[pos], belong);
    len[pos] = len[son[pos]] + 1;
    for(int to : tr[pos])
    {
        if(to == fa[pos][0] || to == son[pos]) continue;
        init_B(to, to);
    }
}
inline void init_C(int pos)
{
    bfs(pos);
    for(int to : tr[pos])
    {
        if(to == fa[pos][0]) continue;
        init_C(to);
    }
}
inline void init_D(int pos)
{
    if(!dfn[pos]) dfn[pos] = ++df_sign, rnk[df_sign] = pos;
    if(son[pos]) init_D(son[pos]);
    for(int to : tr[pos])
    {
        if(to == fa[pos][0] || to == son[pos]) continue;
        init_D(to); 
    }
}
inline void init_E(int pos)
{
    if(dep[pos] - dep[top[pos]] <= d) ++tpA[pos][0], Aid[pos][0] = dfn[pos];
    else ++tpB[pos][0], Bid[pos][0] = dfn[pos];
    min_id[pos][0] = dfn[pos];
    for(int to : tr[pos])
    {
        if(to == fa[pos][0]) continue;
        init_E(to);
        if(far_Aid[to])
        {
            if(!far_Aid[pos]) far_Aid[pos] = far_Aid[to];
            else far_Aid[pos] = min(far_Aid[pos], far_Aid[to]);
        }
        if(far_Bid[to])
        {
            if(!far_Bid[pos]) far_Bid[pos] = far_Bid[to];
            else far_Bid[pos] = min(far_Bid[pos], far_Bid[to]);
        }
        far_tpA[pos] += far_tpA[to];
        far_tpB[pos] += far_tpB[to];
        for(int i = 1; i <= d + 1; ++i)
        {
            if(min_id[to][i - 1])
            {
                if(!min_id[pos][i]) min_id[pos][i] = min_id[to][i - 1];
                else min_id[pos][i] = min(min_id[pos][i], min_id[to][i - 1]);
            }
            if(Aid[to][i - 1])
            {
                if(!Aid[pos][i]) Aid[pos][i] = Aid[to][i - 1];
                else Aid[pos][i] = min(Aid[pos][i], Aid[to][i - 1]);
            }
            if(Bid[to][i - 1])
            {
                if(!Bid[pos][i]) Bid[pos][i] = Bid[to][i - 1];
                else Bid[pos][i] = min(Bid[pos][i], Bid[to][i - 1]);
            }
            tpA[pos][i] += tpA[to][i - 1];
            tpB[pos][i] += tpB[to][i - 1];
        }
        if(Aid[pos][d + 1])
        {
            if(!far_Aid[pos]) far_Aid[pos] = Aid[pos][d + 1];
            else far_Aid[pos] = min(far_Aid[pos], Aid[pos][d + 1]);
        }
        if(Bid[pos][d + 1])
        {
            if(!far_Bid[pos]) far_Bid[pos] = Bid[pos][d + 1];
            else far_Bid[pos] = min(far_Bid[pos], Bid[pos][d + 1]);
        }
    }
    far_tpA[pos] += tpA[pos][d + 1];
    far_tpB[pos] += tpB[pos][d + 1];
}

inline void work_b(int p, int k, Line cur, bool spe = true)
{
//  cerr << "B " << p << " " << k << '\n';
    if(k < 0) return ;
    if(!sum[p][k]) return ;
    if(nxt[p][k] && dep[nxt[p][k]] - dep[top[nxt[p][k]]] > d)
    {
        modify(rt, 1, n, dfn[nxt[p][k]], dfn[nxt[p][k]], cur);
        if(sum[p][k] > 1) modify(rt, 1, n, min_id[p][k], min_id[p][k] + (sum[p][k] - 1) - 1, cur);
    }
    else modify(rt, 1, n, min_id[p][k], min_id[p][k] + sum[p][k] - 1, cur);
}
inline void work_d(int tp, int bt, Line cur)
{
//  cerr << "D " << tp << " " << bt << '\n';
    while(tp != bt && dep[tp] - dep[top[bt]] <= d)
    {
        modify(rt, 1, n, dfn[tp], dfn[tp], cur);
        tp = son[tp];
    }
    modify(rt, 1, n, dfn[tp], dfn[bt], cur);
}

int main()
{
//  freopen("text.in", "r", stdin);
//  freopen("prog.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> Type;
    cin >> n >> m >> d;
    for(int i = 1, x, y; i < n; ++i)
    {
        cin >> x >> y;
        tr[x].push_back(y);
        tr[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i) cin >> org[i];
    init_A(1, 0), init_B(1, 1), init_C(1), init_D(1), init_E(1);
    build(rt, 1, n);
//  cerr << "dfn "; for(int i = 1; i <= n; ++i) cerr << dfn[i] << " "; cerr << '\n';
    for(int t = 1; t <= m; ++t)
    {
        int opt; cin >> opt;
        if(opt == 1)
        {
            int p; cin >> p;
            Line cur = query(rt, 1, n, dfn[p]);
            cout << (org[p] * cur.k + cur.b) % mod << '\n';
        }
        else if(opt == 2)
        {
            int p, dist; Line cur;
            cin >> p >> dist >> cur.k >> cur.b;
            for(int i = 0; i <= dist; ++i)
            {
                if(p >= 1) work_b(p, dist - i, cur), work_b(p, dist - i - 1, cur);
                else work_b(1, dist - i + p - 1, cur), work_b(1, dist - i + p - 2, cur);
                if(p > 1) p = fa[p][0]; else --p;
            }
        }
        else if(opt == 3)
        {
            int p; Line cur;
            cin >> p >> cur.k >> cur.b;
            for(int i = 0; i <= d; ++i) work_b(p, i, cur);
            if(far_tpA[p]) modify(rt, 1, n, far_Aid[p], far_Aid[p] + far_tpA[p] - 1, cur);
            if(far_tpB[p]) modify(rt, 1, n, far_Bid[p], far_Bid[p] + far_tpB[p] - 1, cur);
        }
        else if(opt == 4)
        {
            int x, y; Line cur;
            cin >> x >> y >> cur.k >> cur.b;
            while(top[x] != top[y])
            {
                if(dep[top[x]] < dep[top[y]]) swap(x, y);
                work_d(top[x], x, cur);
                x = fa[top[x]][0];
            }
            if(dep[x] < dep[y]) swap(x, y);
            work_d(y, x, cur);
        }
    }
    return 0;
}
/*
0
23 2 1
1 2
2 3
1 4
3 5
3 6
5 7
7 8
6 9
5 10
5 11
6 12
10 13
8 14
5 15
8 16
10 17
16 18
10 19
7 20
11 21
13 22
16 23
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
3 3 1 6
1 3
*/