题意：四个操作，区间加，区间每个数乘，区间的数变成 2^64-1-x，求区间和。
题解：2^64-1-x=(2^64-1)-x 因为模数为2^64，-x%2^64=-1*x%2^64 由负数取模的性质可知 也就 =(2^64-1)*x%2^64 所以 2^64-1-x=2^64-1+(2^64-1)*x 所以第三个操作也就变成了区间乘 和区间加。 然后就是树剖加线段树多重标记。表示这是第一次写多重标记，整体凭感觉，细节看题解，树剖有点点遗忘，不过还好。今天看群里说邀请赛没什么价值，，细想一下那些题确实裸了点，的确网络赛难啊QAQ。今天好颓，王者玩了好久。
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ls x<<1
#define rs x<<1|1
#define ull unsigned long long
#define _mp make_pair
#define ldb long double
using namespace std;
const int maxn=1e5+100;
const ull inf=(1<<64)-1;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}struct node
{
int l,r;
ull sum,add,mul;
}no[maxn<<2];
int siz[maxn],depth[maxn],dfn[maxn],id[maxn],son[maxn],top[maxn],fa[maxn];
int tot;
vector<int>g[maxn];
int n,m;
void dfs1(int x,int f)
{
depth[x]=depth[f]+1;
fa[x]=f;
siz[x]=1;
for(int i=0;i<(int)g[x].size();i++)
{
int v=g[x][i];
if(v==f)continue;
dfs1(v,x);
siz[x]+=siz[v];
if(son[x]==-1||siz[son[x]]<siz[v])son[x]=v;
}
}
void dfs2(int x,int f)
{
top[x]=f;
id[x]=++tot;
if(son[x]==-1)return;
dfs2(son[x],f);
for(int i=0;i<(int)g[x].size();i++)
{
if(g[x][i]==son[x]||g[x][i]==fa[x])continue;
dfs2(g[x][i],g[x][i]);
}
}
void push_up(int x)
{
no[x].sum=no[x<<1].sum+no[x<<1|1].sum;
}
void push_down(int x)
{
int len=no[x].r-no[x].l+1;
no[x<<1].add=no[x<<1].add*no[x].mul+no[x].add;
no[x<<1|1].add=no[x<<1|1].add*no[x].mul+no[x].add;
no[x<<1].mul=no[x<<1].mul*no[x].mul;
no[x<<1|1].mul=no[x<<1|1].mul*no[x].mul;
no[x<<1].sum=no[x<<1].sum*no[x].mul+(len-(len>>1))*no[x].add;
no[x<<1|1].sum=no[x<<1|1].sum*no[x].mul+((len>>1))*no[x].add;
no[x].add=0;no[x].mul=1;
}
void build(int x,int l,int r)
{
no[x].l=l;no[x].r=r;
no[x].add=0;no[x].mul=1;
no[x].sum=0;
if(l==r)return;
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
}
ull query(int x,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
return no[x].sum;
}
ull res=0;
push_down(x);
int mid=(l+r)>>1;
if(L<=mid)res+=query(ls,l,mid,L,R);
if(R>mid) res+=query(rs,mid+1,r,L,R);
return res;
}
void update(int x,int l,int r,int L,int R,int type,ull v)
{
if(L<=l&&r<=R)
{
if(type==1)
{
no[x].sum=no[x].sum*v;
no[x].add=no[x].add*v;
no[x].mul=no[x].mul*v;
return;
}
if(type==2)
{
no[x].sum+=v*(r-l+1);
no[x].add+=v;
return;
}
if(type==3)
{
no[x].sum=no[x].sum*inf+inf*(r-l+1);
no[x].add=no[x].add*inf+inf;
no[x].mul=no[x].mul*inf;
return;
}
}
push_down(x);
int mid=(l+r)>>1;
if(L<=mid)update(ls,l,mid,L,R,type,v);
if(R>mid)update(rs,mid+1,r,L,R,type,v);
push_up(x);
}
void ask1(int x,int y,int type,ull val)
{
int xx=top[x],yy=top[y];
while(xx!=yy)
{
if(depth[xx]<depth[yy])swap(xx,yy),swap(x,y);
update(1,1,n,id[xx],id[x],type,val);
x=fa[xx];
xx=top[x];
}
if(depth[x]<depth[y])swap(x,y);
update(1,1,n,id[y],id[x],type,val);
}
ull ask2(int x,int y)
{
int xx=top[x],yy=top[y];
ull aa=0;
while(xx!=yy)
{
if(depth[xx]<depth[yy])swap(xx,yy),swap(x,y);
aa+=query(1,1,n,id[xx],id[x]);
x=fa[xx];
xx=top[x];
}
if(depth[x]<depth[y])swap(x,y);
aa+=query(1,1,n,id[y],id[x]);
return aa;
}
void init()
{
for(int i=1;i<=n;i++)g[i].clear();
memset(fa,0,sizeof(fa));
memset(son,-1,sizeof(son));
memset(depth,0,sizeof(depth));
tot=0;
}
int main()
{
while(~scanf("%d",&n))
{
init();
int tmp;
for(int i=2;i<=n;i++)
{
scanf("%d",&tmp);
g[tmp].pb(i);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
scanf("%d",&m);
int pp,qq,rr;
ull s;
for(int i=1;i<=m;i++)
{
scanf("%d",&tmp);
if(tmp==1||tmp==2)
{
scanf("%d%d%llu",&pp,&qq,&s);
ask1(pp,qq,tmp,s);
}
else if(tmp==3)
{
scanf("%d%d",&pp,&qq);
ask1(pp,qq,tmp,0);
}
else
{
scanf("%d%d",&pp,&qq);
cout<<ask2(pp,qq)<<"
";
}
}
}
}