板子
善用 Ctrl+F
快读
template<typename T>void read(T &x)
{
T f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
x*=f;
}快输
template<typename T>void print(T x) {
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+'0');
}压位高精(vector)
struct Int:vector<int>
{
Int(int n=0){push_back(n);check();}
Int& check()
{
while(!empty()&&!back())pop_back();
if(empty())return *this;
for(int i=1;i<size();i++){(*this)[i]+=(*this)[i-1]/10;(*this)[i-1]%=10;}
while(back()>=10){push_back(back()/10);(*this)[size()-2]%=10;}
return *this;
}
};
istream& operator>>(istream &is,Int &n)
{
string s;is>>s;n.clear();
for(int i=s.size()-1;i>=0;i--)n.push_back(s[i]-'0');
return is;
}
ostream& operator<<(ostream &os,const Int &n)
{
if(n.empty())os<<0;
else for(int i=n.size()-1;i>=0;i--)os<<n[i];
return os;
}
bool operator!=(const Int &a,const Int &b)
{
if(a.size()!=b.size())return 1;
for(int i=a.size()-1;i>=0;i--)if(a[i]!=b[i])return 1;
return 0;
}
bool operator==(const Int &a,const Int &b){return !(a!=b);}
bool operator<(const Int &a,const Int &b)
{
if(a.size()!=b.size())return a.size()<b.size();
for(int i=a.size()-1; i>=0; --i)if(a[i]!=b[i])return a[i]<b[i];
return 0;
}
bool operator>(const Int &a,const Int &b){return b<a;}
bool operator<=(const Int &a,const Int &b){return !(a>b);}
bool operator>=(const Int &a,const Int &b){return !(a<b);}
Int& operator+=(Int &a,const Int &b)
{
if(a.size()<b.size())a.resize(b.size());
for(int i=0; i!=b.size(); ++i)a[i]+=b[i];
return a.check();
}
Int operator+(Int a,const Int &b){return a+=b;}
Int& operator-=(Int &a,Int b)
{
for(int i=0; i!=b.size(); a[i]-=b[i],++i)
if(a[i]<b[i])
{
int j=i+1;
while(!a[j])++j;
while(j>i){--a[j];a[--j]+=10;}
}
return a.check();
}
Int operator-(Int a,const Int &b){return a-=b;}
Int operator*(const Int &a,const Int &b)
{
Int n;
n.assign(a.size()+b.size()-1,0);for(int i=0;i!=a.size();i++)for(int j=0;j!=b.size();j++)n[i+j]+=a[i]*b[j];
return n.check();
}
Int& operator*=(Int &a,const Int &b){return a=a*b;}
Int divmod(Int &a,const Int &b)
{
Int ans;
for(int t=a.size()-b.size(); a>=b; --t)
{
Int d;d.assign(t+1,0);d.back()=1;
Int c=b*d;
while(a>=c)
{a-=c;ans+=d;}
}
return ans;
}
Int operator/(Int a,const Int &b){return divmod(a,b);}
Int& operator/=(Int &a,const Int &b){return a=a/b;}
Int& operator%=(Int &a,const Int &b){divmod(a,b);return a;}
Int operator%(Int a,const Int &b){return a%=b;}压位高精（数组，不支持高精除法）
struct Int
{
ll a[10000];int len;
Int() {len=1;memset(a,0,sizeof a);};
void Scan()
{
char str[10000];scanf("%s",str);strin(str);
}
void strin(char *p)
{
int tmpl=strlen(p);
for(int i=tmpl-1;i>=0;i-=8,len++) for(int j=0,rem=1;j<8;j++,rem*=10) (i>=j) ? a[len]+=((*(p+i-j))-'0')*rem:0;
len--;
return;
}
void Cls()
{
while(!a[len] && len!=1) len--;
while(a[len+1]) len++;
return ;
}
void Print()
{
Cls(); printf("%lld",a[len]);
for(int i=len-1;i>0;--i) printf("%08lld",a[i]);
return;
}
int operator = (const int B)
{
len=1;
if(B>=100000000) a[len]=100000000,a[++len]=B%100000000;else a[len]=B;
return B;
}
bool operator < (const Int & B)
{
if(len!=B.len) return len < B.len;
for(int i=len;i>0;--i) if(a[i] != B.a[i]) return a[i] < B.a[i];
return 0;
}
bool operator == (const Int & B)
{
if(len!=B.len) return 0;
for(int i=len;i>0;--i) if(a[i]!=B.a[i]) return 0;
return 1;
}
bool operator <= (const Int & B) {return ((*this)<B)||((*this)==B);}
bool operator > (const Int & B) {return !((*this)<=B);}
bool operator >= (const Int & B) {return !((*this)<B);}
bool operator != (const Int & B) {return !((*this)==B);}
bool operator < (const int & B) {return (a[2]*100000000+a[1]<B);}
bool operator == (const int & B) {return (a[2]*100000000+a[1]==B);}
bool operator <= (const int & B) {return ((*this)<B)||((*this)==B);}
bool operator > (const int & B) {return !((*this)<=B);}
bool operator >= (const int & B) {return !((*this)<B);}
bool operator != (const int & B) {return !((*this)==B);}
Int operator - (const Int & B)
{
Int ret=*this;
for (int i=1;i<=len && i<=B.len;++i)
{
if(ret.a[i] < B.a[i]) ret.a[i] += 100000000,--ret.a[i+1];
ret.a[i] -= B.a[i];
}
ret.Cls();return ret;
}
Int operator + (const Int & B)
{
Int ret=*this;
for (int i=1;i<=len && i<=B.len;++i)
{
if(ret.a[i]+B.a[i] >= 100000000) ret.a[i] -= 100000000,++ret.a[i+1];
ret.a[i] += B.a[i];
}
ret.Cls();return ret;
}
Int operator * (const int & B)
{
Int ret=*this;
for (int i=1;i<=len;++i) ret.a[i] *= B;
for (int i=1;i<=len;++i) ret.a[i+1] += ret.a[i] / 100000000,ret.a[i] %= 100000000;
ret.Cls(); return ret;
}
Int operator * (const Int & B)
{
Int ret;
for (int i=1;i<=len;++i)
for (int j=1;j<=B.len;++j)
ret.a[i+j-1] += a[i] * B.a[j];
for (int i=1;i<len+B.len-1;++i) ret.a[i+1] += ret.a[i] / 100000000,ret.a[i] %= 100000000;
for (ret.len=len+B.len-1;ret.a[ret.len] > 100000000; ++ret.len)
{
ret.a[ret.len+1] += ret.a[ret.len] / 100000000,ret.a[ret.len] %= 100000000;
}
ret.Cls(); return ret;
}
Int operator / (const int & B)
{
Int ret=*this;
for (int i=ret.len;i>0;--i) ret.a[i-1] += (ret.a[i] % B) * 100000000,ret.a[i] /= B;
ret.Cls(); return ret;
}
Int operator -=(Int &A,Int &B){return A=A-B;}
Int operator +=(Int &A,Int &B){return A=A+B;}
Int operator *=(Int &A,Int &B){return A=A*B;}
friend Int gcd(Int xx,Int yy)
{
Int ret;ret=1;
while(xx != yy)
{
while(!(xx.a[1]&1) && !(yy.a[1]&1)) xx=xx/2,yy=yy/2,ret=ret*2;
while(!(xx.a[1]&1)) xx=xx/2;
while(!(yy.a[1]&1)) yy=yy/2;
if(xx < yy) {swap(xx,yy);}
if(xx == yy) break ;
xx=xx-yy;
}
ret = ret*xx;
return ret;
}
};Splay （循环）
struct Node {
int fa,ch[2],val,cnt,sz;
}spl[MAXN];
int n,root,cnt,ans;
void update(int x) {spl[x].sz=spl[spl[x].ch[0]].sz+spl[spl[x].ch[1]].sz+spl[x].cnt;}
bool ident(int x,int f) {return spl[f].ch[1] ==x;}
void connect(int x,int f,int s)
{
spl[f].ch[s]=x;
spl[x].fa=f;
}
void rotate(int x)
{
int f=spl[x].fa,ff=spl[f].fa,k=ident(x,f);
connect(spl[x].ch[k^1],f,k);
connect(x,ff,ident(f,ff));
connect(f,x,k^1);
update(f),update(x);
}
void splaying(int x,int goal)
{
if(!goal) root=x;
while(spl[x].fa!=goal)
{
int f=spl[x].fa,ff=spl[f].fa;
if(ff!=goal) ident(f,ff)^ident(x,f)?rotate(x):rotate(f);
rotate(x);
}
}
void newnode(int &now,int fa,int val)
{
spl[now=++cnt].val=val;
spl[now].fa=fa;
spl[now].sz=spl[now].cnt=1;
}
void ins(int val,int &now=root,int fa=0)
{
if(!now) newnode(now,fa,val),splaying(now,0);
else if(val<spl[now].val) ins(val,spl[now].ch[0],now);
else if(val>spl[now].val) ins(val,spl[now].ch[1],now);
else spl[now].cnt++,spl[now].sz++,splaying(now,0);
}
int getrank(int val)
{
int x=root,rank=1;
while(x)
{
if(spl[x].val==val)
{
rank+=spl[spl[x].ch[0]].sz;
splaying(x,0);
break;
}
if(val<=spl[x].val) x=spl[x].ch[0];
else
{
rank+=spl[spl[x].ch[0]].sz+spl[x].cnt;
x=spl[x].ch[1];
}
}
return rank;
}
int getnum(int rank)
{
int x=root;
while(x)
{
int lsz=spl[spl[x].ch[0]].sz;
if(lsz+1<=rank&&rank<=lsz+spl[x].cnt)
{
splaying(x,0);
break;
}
else if(lsz>=rank) x=spl[x].ch[0];
else
{
rank-=lsz+spl[x].cnt;
x=spl[x].ch[1];
}
}
return spl[x].val;
}
void Find(int x)
{
int u=root;
if(!u) return;
while(spl[u].ch[x>spl[u].val]&&spl[x].val!=x) u=spl[u].ch[x>spl[u].val];
splaying(u,0);
}
int getid(int x)
{
int now=root;
while(now)
{
if(x==spl[now].val) return now;
else now=spl[now].ch[x>spl[now].val];
}
}
void delnode(int x)
{
splaying(x,0);
if(spl[x].cnt>1) spl[x].cnt--,spl[x].sz--,splaying(x,0);
else if(spl[x].ch[1])
{
int p=spl[x].ch[1];
while(spl[p].ch[0]) p=spl[p].ch[0];
splaying(p,x);
connect(spl[x].ch[0],p,0);
root=p;
spl[p].fa=0;
update(root);
}
else root=spl[x].ch[0],spl[root].fa=0;
}
void del(int val,int now=root)
{
if(val==spl[now].val) delnode(now);
else if(val<spl[now].val) del(val,spl[now].ch[0]);
else del(val,spl[now].ch[1]);
}
int Next(int x,int f)
{
Find(x);
int u=root;
if((spl[u].val>x&&f)||(spl[u].val<x&&!f)) return u;
u=spl[u].ch[f];
while(spl[u].ch[f^1]) u=spl[u].ch[f^1];
}Splay （递归）
struct node{
int val,l,r,size,cnt;
}spl[MAXN];
int cnt,root;
void newNode(int &now,int &val)
{
spl[now=++cnt].size++;
spl[cnt].val=val;
spl[cnt].cnt++;
}
void update(int now){spl[now].size=spl[spl[now].l].size+spl[spl[now].r].size+spl[now].cnt;}
void zig(int &now)
{
int l=spl[now].l;
spl[now].l=spl[l].r;
spl[l].r=now;
now=l;
update(spl[now].r);update(now);
}
void zag(int &now)
{
int r=spl[now].r;
spl[now].r=spl[r].l;
spl[r].l=now;
now=r;
update(spl[now].l);update(now);
}
void splaying(int x,int &y)
{
if(x==y) return;
int &l=spl[y].l,&r=spl[y].r;
if(x==l) zig(y);
else if(x==r) zag(y);
else
{
if(spl[x].val<spl[y].val)
{
if(spl[x].val<spl[l].val) splaying(x,spl[l].l),zig(y),zig(y);
else splaying(x,spl[l].r),zag(l),zig(y);
}
else
{
if(spl[x].val>spl[r].val) splaying(x,spl[r].r),zag(y),zag(y);
else splaying(x,spl[r].l),zig(r),zag(y);
}
}
}
void delNode(int &now)
{
splaying(now,root);
if(spl[now].cnt>1) spl[now].cnt--,spl[now].size--;
else if(spl[root].r)
{
int p=spl[root].r;
while(spl[p].l) p=spl[p].l;
splaying(p,spl[root].r);
spl[spl[root].r].l=spl[root].l;
root=spl[root].r;
update(root);
}
else root=spl[root].l;
}
void insert(int &now,int val)
{
if(!now) newNode(now,val),splaying(now,root);
else if(spl[now].val>val) insert(spl[now].l,val);
else if(spl[now].val<val) insert(spl[now].r,val);
else spl[now].size++,spl[now].cnt++,splaying(now,root);
}
void del(int now,int &val)
{
if(spl[now].val==val) delNode(now);
else if(spl[now].val>val) del(spl[now].l,val);
else del(spl[now].r,val);
}
int getrank(int val)
{
int now=root,rank=1;
while(now)
{
if(spl[now].val==val)
{
rank+=spl[spl[now].l].size;
splaying(now,root);
return rank;
}
if(spl[now].val<val)
{
rank+=spl[spl[now].l].size+spl[now].cnt;
now=spl[now].r;
}
else now=spl[now].l;
}
return rank;
}
int getval(int rank)
{
int now=root;
while(now)
{
int lsize=spl[spl[now].l].size;
if(lsize+1<=rank&&rank<=lsize+spl[now].cnt)
{
splaying(now,root);
return spl[now].val;
}
if(lsize<rank)
{
rank-=lsize+spl[now].cnt;
now=spl[now].r;
}
else now=spl[now].l;
}
return spl[now].val;
}树剖(带换根)
#include <cstdio>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
const int MAXN=_______;
int val[MAXN],w[MAXN],f[MAXN][20],lg[MAXN];
int siz[MAXN],son[MAXN],fa[MAXN],dep[MAXN];
vector <int> G[MAXN];
struct Seg{
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
ll tr[MAXN<<2],tag[MAXN<<2];
void push_up(int p){tr[p]=tr[ls]+tr[rs];}
void push_down(int p,int l,int r)
{
if(!tag[p]) return;
int mid=(l+r)>>1;
tag[ls]=(tag[ls]+tag[p]); tr[ls]+=(mid-l+1)*tag[p];
tag[rs]=(tag[rs]+tag[p]); tr[rs]+=(r-mid)*tag[p];
tag[p]=0;
}
void build(int p,int l,int r)
{
if(l==r)
{
tr[p]=w[l];
return;
}
int mid=(l+r)>>1;
build(lson);build(rson);
push_up(p);
}
void modify(int p,int l,int r,int l_x,int r_x,int val)
{
if(l_x<=l&&r<=r_x)
{
tag[p]+=val;
tr[p]+=(r-l+1)*val;
return;
}
int mid=(l+r)>>1;
push_down(p,l,r);
if(l_x<=mid) modify(lson,l_x,r_x,val);
if(mid<r_x) modify(rson,l_x,r_x,val);
push_up(p);
}
ll query(int p,int l,int r,int l_x,int r_x)
{
ll ret=0;
if(l_x<=l&&r<=r_x) return tr[p];
int mid=(l+r)>>1;
push_down(p,l,r);
if(l_x<=mid) (ret+=query(lson,l_x,r_x));
if(mid<r_x) (ret+=query(rson,l_x,r_x));
return ret;
}
}seg;
void dfs1(int u,int fat)
{
siz[u]=1;
fa[u]=fat;
dep[u]=dep[fat]+1;
f[u][0]=fat;
for(int i=1;i<=lg[dep[u]];i++) f[u][i]=f[f[u][i-1]][i-1];
int tmp=-1;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==fat) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(tmp<siz[v])
{
tmp=siz[v];
son[u]=v;
}
}
}
int times,dfn[MAXN],top[MAXN];
void dfs2(int u,int t)
{
top[u]=t;
dfn[u]=++times;
w[times]=val[u];
if(!son[u]) return;
dfs2(son[u],t);
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
ll LCA(ll x,ll y)
{
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=f[x][lg[dep[x]-dep[y]]-1];
if(x==y) return x;
for(ll k=lg[dep[x]]-1;k>=0;k--)
{
if(f[x][k]!=f[y][k]) x=f[x][k],y=f[y][k];
}
return f[x][0];
}
int main() {
// freopen("tree1.in","r",stdin);
// freopen("tree1.ans","w",stdout);
int n,m,root;
scanf("%d",&n);
root=1;
for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i),scanf("%d",&val[i]);
for(int i=2,u;i<=n;i++)
{
scanf("%d",&u);
G[u].push_back(i);
G[i].push_back(u);
}
dfs1(root,0);
dfs2(root,root);
seg.build(1,1,n);
ll op,x,y,now=root;
ll val;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%lld %lld",&op,&x);
if(op==1) now=x;
if(op==2)
{
scanf("%lld %lld",&y,&val);
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
seg.modify(1,1,n,dfn[top[x]],dfn[x],val);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
seg.modify(1,1,n,dfn[x],dfn[y],val);
}
if(op==3)
{
scanf("%lld",&val);
ll tmp=now;
ll lca=LCA(tmp,x);
if(now==x) seg.modify(1,1,n,dfn[1],dfn[1]+siz[1]-1,val);
else if(lca==x)
{
for(int i=lg[dep[tmp]]-1;i>=0;i--)
{
if(dep[f[tmp][i]]>dep[x]) tmp=f[tmp][i];
}
seg.modify(1,1,n,dfn[tmp]+siz[tmp],n,val);
seg.modify(1,1,n,1,dfn[tmp]-1,val);
}
else seg.modify(1,1,n,dfn[x],dfn[x]+siz[x]-1,val);
}
if(op==4)
{
ll ans=0;
scanf("%lld",&y);
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=seg.query(1,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=seg.query(1,1,n,dfn[x],dfn[y]);
printf("%lld\n",ans);
}
if(op==5)
{
ll ans=0,tmp=now;
ll lca=LCA(tmp,x);
if(now==x) ans+=seg.query(1,1,n,dfn[1],dfn[1]+siz[1]-1);
else if(lca==x)
{
for(int i=lg[dep[tmp]]-1;i>=0;i--)
{
if(dep[f[tmp][i]]>dep[x]) tmp=f[tmp][i];
}
ans+=seg.query(1,1,n,dfn[tmp]+siz[tmp],n);
ans+=seg.query(1,1,n,1,dfn[tmp]-1);
}
else ans+=seg.query(1,1,n,dfn[x],dfn[x]+siz[x]-1);
printf("%lld\n",ans);
}
}
return 0;
}FHQ-Treap
struct FHQ_Treap{
#define ls lson[p]
#define rs rson[p]
int tot,root,x,y,z;
int lson[MAXN],rson[MAXN],val[MAXN],pri[MAXN],siz[MAXN];
void Update(int p){siz[p]=siz[ls]+siz[rs]+1;}
void Split(int p,int v,int &x,int &y)
{
if(!p)
{
x=y=0;
return;
}
if(val[p]<=v) x=p,Split(rs,v,rs,y);
else y=p,Split(ls,v,x,ls);
Update(p);
}
int Merge(int u,int v)
{
if(!u||!v) return u|v;
if(pri[u]<pri[v])
{
rson[u]=Merge(rson[u],v);
Update(u);
return u;
}
else
{
lson[v]=Merge(u,lson[v]);
Update(v);
return v;
}
}
int NewNode(int x){val[++tot]=x;siz[tot]=1;pri[tot]=rand();return tot;}
void Insert(int Val)
{
Split(root,Val,x,y);
root=Merge(Merge(x,NewNode(Val)),y);
}
void Delete(int Val)
{
Split(root,Val,x,z);
Split(x,Val-1,x,y);
y=Merge(lson[y],rson[y]);
root=Merge(Merge(x,y),z);
}
int GetRank(int Val)
{
Split(root,Val-1,x,y);
int ret=siz[x]+1;
root=Merge(x,y);
return ret;
}
int GetVal(int Rank)
{
int p=root;
while(p)
{
if(siz[ls]+1==Rank) break;
if(siz[ls]<Rank) Rank-=siz[ls]+1,p=rs;
else p=ls;
}
return val[p];
}
}Tr;