一类爆改 dfs 序使得树剖支持邻域操作的方法。
_determination_
·
·
算法·理论
这个科技似乎叫毛毛虫剖分吗？我听别人这么说的。
由于作者是跟着这篇文章学的，所以可能有点像请见谅。
模拟赛以前就看见上面那篇文章了，可惜没认真看不会做整道题，只好打暴力了/ll
赛后出题人跟我说我写的性质随便扩展一下就是正解了，于是被加封为赤石大王。。。
:::info[例题]
给你一棵树，树的根为 1，初始时每个点都有一个点权，要求进行以下操作：
- 查询某个点的点权，对 998244353 取模。
- 使 x 的子树里的所有点的点权 v 变成 kv+b。
- 使与 x 的距离小于等于 d 的点的点权 v 变成 kv+b。这里 x 与 y 的距离定义为路径上的边数。
- 使 x 到 y 路径上的点的点权 v 变成 kv+b。
:::
显然如果没有 3 操作就是树剖板子套上线段树 2。如果修改操作的 $k$ 固定为 1 也可以直接套上 P9527。但是这里的操作不满足交换律，于是我们不得不考虑直接维护。
类似 P9527 的，邻域操作可以转化为 $O(K)$ 次对某个节点往下的第 $x$ 层操作。我们需要一个既部分满足重链剖分重链编号连续，也要部分满足 bfs 序某一层编号连续，还要满足子树编号连续的性质。显然这些性质做不到同时满足，但是我们每次操作都有 $O(K)$ 的容错拿来给你跑暴力。于是我们考虑爆改 dfs 序。
我们考虑这样对树上的点分类：
* 先划分出重链并求出每个点的 top。
* 每条重链上的前 $K$ 个点称为 A 类点，其余点称为 B 类点。
然后我们进行这样的操作：
* dfs 整棵树，每 dfs 到一个节点就进行一次 bfs。
* bfs 是这样的：只能向儿子扩展，到与起点距离大于 K 的时候结束。如果遇到了一个 A 类点没有过编号，给他一个编号。
* 这时候我们就给全部的 A 类点编号了。
* 再进行一次 dfs。到达一个节点的时候若没有标号则给他一个新的标号。
* 递归规则就像正常重剖的 dfs2 一样。
* 此时我们给所有 B 类点标号完毕，整棵树标号完毕。
他有这样的性质：
* A 类点标号全在 B 类点之前。这个显然。
* 满足每个点往下走 $d(d\le K)$ 次所在一层最多只有一个 B 类点，并且所有 A 类点的标号连续。
:::info[证明]
先来证最多只有一个 B 类点。
由于 $d\le K$，所以 B 类点一定是从 x 所在重链一直拉下来的。在中间任何位置断掉都会让他不是 B 类点。
所有 A 类点标号连续是显然的，这里就不证了。
:::
* 一条重链上只有 A 类点的编号不连续。这个显然。
* 一棵子树里的编号除去前 K 层之后会划分为两个区间，一个是由 A 类点组成的区间，一个是由 B 类点组成的区间，中间没有断点。自己研究一下标号过程即可发现这是对的。
那么我们已经得到了解决这道题所需的全部性质。然后我们就开始考虑代码实现了。
这里先放出代码然后逐函数数组解释。
:::info[代码]
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
const int N=1e5+10,M=110;
int n,a[N],K,c,m;
vector<int>e[N];
int fa[N],son[N],siz[N],dep[N];
int sum[N][M];
void dfs1(int x,int f)
{
fa[x]=f,dep[x]=dep[f]+1,siz[x]=1;sum[x][0]=1;
for ( auto v:e[x] )
{
if(v==f)continue;
dfs1(v,x);siz[x]+=siz[v];
if(siz[son[x]]<siz[v])son[x]=v;
for ( int i = 1 ; i <= K ; i++ )sum[x][i]+=sum[v][i-1];
}
}
int dfn[N],tot,bef[N],top[N];
int kson[N][M],len[N];
void dfs2A(int x,int head)
{
if(!x)return;
top[x]=head;kson[x][0]=x,len[x]=1;
dfs2A(son[x],head);
for ( int i = 1 ; i <= K ; i++ )kson[x][i]=kson[son[x]][i-1];
len[x]=len[son[x]]+1;
for ( auto v:e[x] )if(v!=son[x]&&v!=fa[x])dfs2A(v,v);
}
queue<int>q;
void bfs(int s)
{
q.push(s);
while(!q.empty())
{
int x=q.front();q.pop();
if(dep[x]-dep[top[x]]<=K)
if(!dfn[x]){dfn[x]=++tot;bef[tot]=x;}
if(dep[x]-dep[s]==K)continue;
for ( auto v:e[x] )if(v!=fa[x])q.push(v);
}
}
void dfs2B(int x)
{
bfs(x);
for ( auto v:e[x] )if(v!=fa[x])dfs2B(v);
}
void dfs2C(int x)
{
if(!x)return;
if(!dfn[x]){dfn[x]=++tot;bef[tot]=x;}
dfs2C(son[x]);
for ( auto v:e[x] )if(v!=fa[x]&&v!=son[x])dfs2C(v);
}
int Aid[N][M],Bid[N][M],cntA[N][M],cntB[N][M];
int farAid[N],farBid[N],farAcnt[N],farBcnt[N];
int minid[N][M];
void getmin(int &x,int y){x=min(x,y);}
void dfs3(int x)
{
minid[x][0]=dfn[x];
if(dep[x]-dep[top[x]]<=K)Aid[x][0]=dfn[x],cntA[x][0]=1;
else Bid[x][0]=dfn[x],cntB[x][0]=1;
for ( auto v:e[x] )
{
if(v==fa[x])continue;
dfs3(v);
if(farAid[v])
{
if(farAid[x])getmin(farAid[x],farAid[v]);
else farAid[x]=farAid[v];
}
if(farBid[v])
{
if(farBid[x])getmin(farBid[x],farBid[v]);
else farBid[x]=farBid[v];
}
farAcnt[x]+=farAcnt[v],farBcnt[x]+=farBcnt[v];
for ( int i = 1 ; i <= K+1 ; i++ )
{
if(minid[v][i-1])
{
if(minid[x][i])getmin(minid[x][i],minid[v][i-1]);
else minid[x][i]=minid[v][i-1];
}
if(Aid[v][i-1])
{
if(Aid[x][i])getmin(Aid[x][i],Aid[v][i-1]);
else Aid[x][i]=Aid[v][i-1];
}
if(Bid[v][i-1])
{
if(Bid[x][i])getmin(Bid[x][i],Bid[v][i-1]);
else Bid[x][i]=Bid[v][i-1];
}
cntA[x][i]+=cntA[v][i-1],cntB[x][i]+=cntB[v][i-1];
}
}
if(Aid[x][K+1])
{
if(farAid[x])getmin(farAid[x],Aid[x][K+1]);
else farAid[x]=Aid[x][K+1];
}
if(Bid[x][K+1])
{
if(farBid[x])getmin(farBid[x],Bid[x][K+1]);
else farBid[x]=Bid[x][K+1];
}
farAcnt[x]+=cntA[x][K+1];
farBcnt[x]+=cntB[x][K+1];
}
namespace SGT{
struct node{
int l,r,adt,mut;
}t[N<<2];
void build(int x,int l,int r)
{
t[x]={l,r,0,1};
if(l==r)return t[x].adt=a[bef[l]],void();
int mid=(l+r)/2;
build(x<<1,l,mid),build(x<<1|1,mid+1,r);
}
void mkadt(int x,int v){t[x].adt=(t[x].adt+v)%mod;}
void mkmut(int x,int v){t[x].adt=t[x].adt*v%mod,t[x].mut=t[x].mut*v%mod;}
void pd(int x)
{
if(t[x].mut!=1)
{
mkmut(x<<1,t[x].mut);
mkmut(x<<1|1,t[x].mut);
t[x].mut=1;
}
if(t[x].adt!=0)
{
mkadt(x<<1,t[x].adt);
mkadt(x<<1|1,t[x].adt);
t[x].adt=0;
}
}
void update(int x,int l,int r,int mv,int av)
{
if(l>r)return;
int lf=t[x].l,rt=t[x].r;
if(l<=lf&&rt<=r)return mkmut(x,mv),mkadt(x,av);
if(rt<l||r<lf)return;
pd(x);update(x<<1,l,r,mv,av),update(x<<1|1,l,r,mv,av);
}
int query(int x,int p)
{
int lf=t[x].l,rt=t[x].r;
if(lf==rt)return t[x].adt;
pd(x);int mid=(lf+rt)/2;
if(p<=mid)return query(x<<1,p);
else return query(x<<1|1,p);
}
}
void updateA(int x,int d,int k,int b)
{
if(k<0)return;
if(!sum[x][d])return;
if(kson[x][d]&&dep[kson[x][d]]-dep[top[kson[x][d]]]>K)
{
SGT::update(1,dfn[kson[x][d]],dfn[kson[x][d]],k,b);
if(sum[x][d]>1)SGT::update(1,minid[x][d],minid[x][d]+sum[x][d]-2,k,b);
}else SGT::update(1,minid[x][d],minid[x][d]+sum[x][d]-1,k,b);
}
void updateB(int x,int y,int k,int b)
{
while(dep[x]-dep[top[x]]<=K&&x!=y)
{
SGT::update(1,dfn[x],dfn[x],k,b);
x=son[x];
}
SGT::update(1,dfn[x],dfn[y],k,b);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
// freopen("tree.in","r",stdin);
// freopen("tree.out","w",stdout);
cin >> c >> n >> m >> K;
for ( int i = 1 ; i < n ; i++ )
{
int u,v;cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
for ( int i = 1 ; i <= n ; i++ )cin >> a[i];
dfs1(1,1);dfs2A(1,1);dfs2B(1);dfs2C(1);dfs3(1);
SGT::build(1,1,n);
while(m--)
{
int op,x,k,p,q;
cin >> op;
if(op==1)
{
cin >> x;
cout << SGT::query(1,dfn[x]) << endl;
}else if(op==2){
cin >> x >> k >> p >> q;
while(1)
{
updateA(x,k,p,q);
if(!k)break;k--;
updateA(x,k,p,q);
if(x==1)
{
while(k--)updateA(x,k,p,q);
break;
}x=fa[x];
}
}else if(op==3)
{
cin >> x >> p >> q;
for ( int i = 0 ; i <= K ; i++ )updateA(x,i,p,q);
if(farAcnt[x])SGT::update(1,farAid[x],farAid[x]+farAcnt[x]-1,p,q);
if(farBcnt[x])SGT::update(1,farBid[x],farBid[x]+farBcnt[x]-1,p,q);
}else{
cin >> x >> k >> p >> q;
while(top[x]!=top[k])
{
if(dep[top[x]]<dep[top[k]])swap(x,k);
updateB(top[x],x,p,q);
x=fa[top[x]];
}
if(dep[x]>dep[k])swap(x,k);
updateB(x,k,p,q);
}
}
return 0;
}
```
:::
`namespace SGT` 就是正常的线段树 2。不需要管。
数组：
* 这里先解释变量，然后在后面部分解释求法。
* `fa[],son[],siz[],dep[],dfn[],bef[],top[]` 与正常树剖的意义相同，这里不解释。
* `sum[x][y]` 表示 $x$ 往下走 $y$ 步所在层一共有多少个点。
* `minid[x][y]` 表示 $x$ 往下走 $y$ 步这一层的点编号最小是多少。
* `kson[x][y]` 表示 $x$ 沿着重儿子往下走 $y$ 步所在的点是什么。显然只有这个可能是该层的唯一 B 类点。
* `len[]` 表示该点沿着重儿子往下走这条链的长度（点数）。
* `A/Bid[x][y],cntA/B[x][y]` 分别表示 $x$ 往下走 $y$ 步所在层的 A/B 类点的最小编号和数量。
* `farA/Bid[x],farA/Bcnt[x]` 分别表示 $x$ 往下走 $K$ 步以上那些部分 A/B 类点的最小编号和数量。
函数：
* `updateA(int x,int d,int p,int q)` 将 $x$ 往下 $d$ 步那一层做修改，$p,q$ 为修改参数。之后的函数同样。为了完成这个函数，我们直接调用 `kson` 来找到 B 类点，然后区间修改剩下的 A 类点。
* `update(int x,int y,int p,int q)` 将 $x$ 到 $y$ 这条重链的所有点做修改。保证 $x$ 在 $y$ 上面并且他们在一条重链上。实现方法就是从 $x$ 一直往下沿着重儿子跳直到跳到 B 类点然后直接区修，中间经过的部分可以直接单修。
* `dfs1` 求出了 `dep,top,son,fa,sum` 等基本信息。
* `dfs2A` 求出了 `top,kson,len`。
* `dfs2B` 对 A 类点进行标号
* `dfs3` 求出了 `minid,A/Bid,cntA/B,farA/Bid,farA/Bcnt`。
至此，我们完成了这道题并且解释了实现方法。