题面：
有一棵根节点为1的树，初始时节点权值均为0
可执行的操作：
x到y路径上的节点权值全部乘以一个数z
x到y路径上的节点权值全部加上一个数z
x到y路径上的节点权值全部取反
查询x到y路径上的节点权值和。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
namespace onlyzhao
{
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define forhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define one(n) for(int i=1;i<=(n);i++)
#define rone(n) for(int i=(n);i>=1;i--)
#define fone(i,x,n) for(int i=(x);i<=(n);i++)
#define frone(i,n,x) for(int i=(n);i>=(x);i--)
#define fonk(i,x,n,k) for(int i=(x);i<=(n);i+=(k))
#define fronk(i,n,x,k) for(int i=(n);i>=(x);i-=(k))
#define two(n,m) for(int i=1;i<=(n);i++) for(int j=1;j<=(m);j++)
#define ftwo(i,n,j,m) for(int i=1;i<=(n);i++) for(int j=1;j<=(m);j++)
#define cls(a) memset(a,0,sizeof(a))
#define cls1(a) memset(a,-1,sizeof(a))
#define clsmax(a) memset(a,0x3f,sizeof(a))
#define clsmin(a) memset(a,0x80,sizeof(a))
#define cln(a,num) memset(a,0,sizeof(a[0])*num)
#define cln1(a,num) memset(a,-1,sizeof(a[0])*num)
#define clnmax(a,num) memset(a,0x3f,sizeof(a[0])*num)
#define clnmin(a,num) memset(a,0x80,sizeof(a[0])*num)
#define sc(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define scl(x) scanf("%lld",&x)
#define scl2(x,y) scanf("%lld%lld",&x,&y)
#define scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define scf(x) scanf("%lf",&x)
#define scf2(x,y) scanf("%lf%lf",&x,&y)
#define scf3(x,y,z) scanf("%lf%lf%lf",&x,&y,&z)
#define scs(x) scanf("%s",x+1)
#define scs0(x) scanf("%s",x)
#define scline(x) scanf("%[^\n]%*c",x+1)
#define scline0(x) scanf("%[^\n]%*c",x)
#define pcc(x) putchar(x)
#define pc(x) printf("%d\n",x)
#define pc2(x,y) printf("%d %d\n",x,y)
#define pc3(x,y,z) printf("%d %d %d\n",x,y,z)
#define pck(x) printf("%d ",x)
#define pcl(x) printf("%lld\n",x)
#define pcl2(x,y) printf("%lld %lld\n",x,y)
#define pcl3(x,y,z) printf("%lld %lld %d\n",x,y,z)
#define pclk(x) printf("%lld ",x)
#define pcf2(x) printf("%.2f\n",x)
#define pcf6(x) printf("%.6f\n",x)
#define pcf8(x) printf("%.8f\n",x)
#define pcs(x) printf("%s\n",x+1)
#define pcs0(x) printf("%s\n",x)
#define pcline(x) printf("%d**********\n",x)
char buffer[100001],*S,*T;
inline char Get_Char()
{
if (S==T)
{
T=(S=buffer)+fread(buffer,1,100001,stdin);
if (S==T) return EOF;
}
return *S++;
}
inline int read()
{
char c;int re=0;
for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
while(c>='0'&&c<='9') re=re*10+(c-'0'),c=Get_Char();
return re;
}
};
using namespace onlyzhao;
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int maxm=100100;
const int up=100000;
const int hp=13331;
const int maxn=100100;
//取反x -> (2^64-1)- x
//即 x * -1 + (2^64-1)
//其中 -1 == 2^64-1
const llu p=-1ll;
int n,m,r,k;
int head[maxn],ver[maxn],nt[maxn];
int f[maxn],d[maxn],si[maxn],son[maxn],rk[maxn];
int top[maxn],id[maxn];
int tot=1,cnt=0;
void init(void)
{
memset(head,0,sizeof(head));
memset(son,0,sizeof(son));
tot=1,cnt=0;
}
void add(int x,int y)
{
ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
void dfs1(int x,int fa)
{
int max_son=0;
si[x]=1;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y==fa) continue;
f[y]=x;
d[y]=d[x]+1;
dfs1(y,x);
si[x]+=si[y];
if(si[y]>max_son)max_son=si[y],son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
id[x]=++cnt;
rk[cnt]=x;
if(!son[x]) return ;
dfs2(son[x],t);
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y!=son[x]&&y!=f[x])
dfs2(y,y);
}
}
struct node
{
int l,r;
llu sum;
llu mul;
llu add;
}t[maxn<<2];
void pushup(int cnt)
{
t[cnt].sum=t[lc].sum+t[rc].sum;
}
void pushdown(int cnt)
{
if(t[cnt].mul==1&&t[cnt].add==0) return ;
t[lc].sum=t[lc].sum*t[cnt].mul+t[cnt].add*len(lc);
t[rc].sum=t[rc].sum*t[cnt].mul+t[cnt].add*len(rc);
t[lc].mul=t[lc].mul*t[cnt].mul;
t[rc].mul=t[rc].mul*t[cnt].mul;
t[lc].add=t[lc].add*t[cnt].mul+t[cnt].add;
t[rc].add=t[rc].add*t[cnt].mul+t[cnt].add;
t[cnt].add=0;
t[cnt].mul=1;
return ;
}
void build(int l,int r,int cnt)
{
t[cnt].add=0;t[cnt].mul=1;
t[cnt].l=l;t[cnt].r=r;
if(l==r)
{
t[cnt].sum=0;
return ;
}
int mid=(l+r)/2;
build(l,mid,cnt<<1);
build(mid+1,r,cnt<<1|1);
pushup(cnt);
return ;
}
void change(int l,int r,int cnt,ll val,int flag)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
if(flag)
{
t[cnt].sum=t[cnt].sum+len(cnt)*val;
t[cnt].add=t[cnt].add+val;
}
else
{
t[cnt].sum=t[cnt].sum*val;
t[cnt].add=t[cnt].add*val;
t[cnt].mul=t[cnt].mul*val;
}
return ;
}
pushdown(cnt);
if(l<=t[cnt<<1].r) change(l,r,cnt<<1,val,flag);
if(r>=t[cnt<<1|1].l) change(l,r,cnt<<1|1,val,flag);
pushup(cnt);
return ;
}
llu ask(int l,int r,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
return t[cnt].sum;
llu ans=0;
pushdown(cnt);
if(l<=t[cnt<<1].r) ans=ans+ask(l,r,cnt<<1);
if(r>=t[cnt<<1|1].l) ans=ans+ask(l,r,cnt<<1|1);
return ans;
}
void change_road(int x,int y,llu val,int flag)
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
change(id[top[x]],id[x],1,val,flag);
x=f[top[x]];
}
if(id[x]>id[y]) swap(x,y);
change(id[x],id[y],1,val,flag);
}
llu ask_road(int x,int y)
{
llu ans=0;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
ans=ans+ask(id[top[x]],id[x],1);
x=f[top[x]];
}
if(id[x]>id[y]) swap(x,y);
ans=ans+ask(id[x],id[y],1);
return ans;
}
int main(void)
{
while(scanf("%d",&n)!=EOF)
{
init();
int pos,x,y;
llu val;
for(int i=2;i<=n;i++)
{
scanf("%d",&x);
add(x,i);
}
dfs1(1,0);
dfs2(1,1);
build(1,cnt,1);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&pos);
if(pos==1)
{
scanf("%d%d%llu",&x,&y,&val);
change_road(x,y,val,0);
}
else if(pos==2)
{
scanf("%d%d%llu",&x,&y,&val);
change_road(x,y,val,1);
}
else if(pos==3)
{
scanf("%d%d",&x,&y);
change_road(x,y,p,0);
change_road(x,y,p,1);
}
else
{
scanf("%d%d",&x,&y);
printf("%llu\n",ask_road(x,y));
}
}
}
return 0;
}
京公网安备 11010502036488号