\(\text{「CF1491H」Yuezheng Ling and Dynamic Tree}\)
\(\text{Solution}\)
根据弹飞绵羊的思路,考虑分块维护一个 \(\text{top}(u)\) 表示 \(u\) 第一个不在当前块的祖先,设块长为 \(O(B)\),考虑如何求 \(u\) 和 \(v\) 的 \(\text{LCA}\),我们可以用类似于树剖跳重链的方法在 \(O(\dfrac nB+B)\) 求出。考虑如何修改,发现修改操作一定会使 \(a\) 减少,且 \(\text{top(u)}\) 修改 \(O(B)\) 次后一定有 \(\text{top}(u)=a_u\),所以暴力修改,当块内全有 \(\text{top}(i)=a_i\) 时打个标记即可,时间复杂度为 \(O(nB+q(\dfrac{n}{B}+B))\),块长取 \(O(\sqrt{n})\) 即为 \(O((n+q)\sqrt{n})\).
#include<bits/stdc++.h>
#define ll long long
#define PI pair<int,int>
#define PII pair< pair<int,int> , int >
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define MAXN (100005)
#define MAXB (355)
#define MOD (1000000007)
using namespace std;
template<typename type>
void read(type &x)
{
x=0;char ch=0;bool ff=0;
while(ch<'0'||ch>'9'){ff|=!(ch^'-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x=ff?-x:x;
}
ll qpow(ll x,ll y)
{
ll res=1;
while(y)
{
if(y&1ll) res=res*x%MOD;
x=x*x%MOD,y>>=1ll;
}
return res;
}
bool vis[MAXN];
int n,q,lim;
int cnt[MAXB],f[MAXN],top[MAXN],idx[MAXN],l[MAXB],r[MAXB],tag[MAXB];
void rebuild(int x)
{
cnt[x]=0;
for(int i=l[x];i<=r[x];i++)
f[i]=max(f[i]-tag[x],1);
tag[x]=0;
for(int i=l[x];i<=r[x];i++)
{
if(f[i]<l[x]) top[i]=f[i],++cnt[x];
else top[i]=top[f[i]];
}
}
void init()
{
lim=300;
for(int i=1;i<=n;i++)
{
idx[i]=(i+lim-1)/lim;
l[idx[i]]=l[idx[i]]?l[idx[i]]:i;
r[idx[i]]=i;
}
for(int i=1;i<=idx[n];i++)
rebuild(i);
return;
}
void modify(int L,int R,int x)
{
if(idx[L]^idx[R])
{
for(int i=L;i<=r[idx[L]];i++)
f[i]=max(f[i]-x,1);
rebuild(idx[L]);
for(int i=idx[L]+1;i<idx[R];i++)
{
if(cnt[i]<r[i]-l[i]+1)
{
for(int j=l[i];j<=r[i];j++)
f[j]=max(f[j]-x,1);
rebuild(i);
}
else tag[i]=min(tag[i]+x,n);
}
for(int i=l[idx[R]];i<=R;i++)
f[i]=max(f[i]-x,1);
rebuild(idx[R]);
}
else
{
for(int i=L;i<=R;i++)
f[i]=max(f[i]-x,1);
rebuild(idx[L]);
}
}
int topfa(int u){return max(top[u]-tag[idx[u]],1);}
int LCA(int u,int v)
{
while(1)
{
if(idx[u]<idx[v]) swap(u,v);
if(idx[u]^idx[v]) u=topfa(u);
else
{
if(topfa(u)^topfa(v)) u=topfa(u),v=topfa(v);
else break;
}
}
while(u^v)
{
if(u<v) swap(u,v);
u=max(f[u]-tag[idx[u]],1);
}
return u;
}
int main()
{
read(n),read(q);
for(int i=2;i<=n;i++)
read(f[i]);
init();
for(int tq=1;tq<=q;tq++)
{
int opt;
read(opt);
if(!(opt^1))
{
int l,r,x;
read(l),read(r),read(x);
modify(l,r,x);
f[1]=0,top[1]=0;
}
if(!(opt^2))
{
int u,v;
read(u),read(v);
printf("%d\n",LCA(u,v));
}
}
}