Jiu Yuan Wants to Eat

https://nanti.jisuanke.com/t/31714

You ye Jiu yuan is the daughter of the Great GOD Emancipator. And when she becomes an adult, she will be queen of Tusikur, so she wanted to travel the world while she was still young. In a country, she found a small pub called Whitehouse. Just as she was about to go in for a drink, the boss Carola appeared. And ask her to solve this problem or she will not be allowed to enter the pub. The problem description is as follows:

There is a tree with

The answer modulo $2^{64}264.$

Jiu Yuan is a clever girl, but she was not good at algorithm, so she hopes that you can help her solve this problem. Ding $\backsim\backsim\backsim∽∽∽$

The bitwise NOT is a unary operation that performs logical negation on each bit, forming the ones' complement of the given binary value. Bits that are

NOT 0111 (decimal 7) = 1000 (decimal 8)

NOT 10101011 = 01010100

Input

The input contains multiple groups of data.

For each group of data, the first line contains a number of

The second line contains $b_ibi?, which means that the father node of node (i +1)(i+1) is b_ibi?.$

The third line contains one integer

The next

At first, we input one integer opt

$\le n,m,u,v \le 10^51≤n,m,u,v≤105$

$\le x < 2^{64}1≤x<264$

Output

For each operation

样例输入

7
1 1 1 2 2 4
5
2 5 6 1
1 1 6 2
4 5 6
3 5 2
4 2 2
2
1
4
3 1 2
4 1 2
3 1 1
4 1 1

样例输出

5
18446744073709551613
18446744073709551614
0

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

  1 #include<iostream>
  2 #include<cstring>
  3 #include<string>
  4 #include<cmath>
  5 #include<cstdio>
  6 #include<algorithm>
  7 #include<vector>
  8 #define maxn 100005
  9 #define lson l,mid,rt<<1
 10 #define rson mid+1,r,rt<<1|1
 11 typedef unsigned long long ull;
 12 using namespace std;
 13 
 14 ull tree[maxn<<3],lazya[maxn<<3],lazym[maxn<<3];
 15 int n;
 16 ull v[maxn],val[maxn];
 17 int dep[maxn],fa[maxn],siz[maxn],son[maxn],id[maxn],top[maxn],cnt;
 18 vector<ull>ve[maxn];
 19 
 20 void pushup(int rt){
 21     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
 22 }
 23 
 24 void pushdown(int len,int rt){
 25     if(lazya[rt]||lazym[rt]!=1){
 26         lazym[rt<<1]*=lazym[rt];
 27         lazym[rt<<1|1]*=lazym[rt];
 28         lazya[rt<<1]*=lazym[rt];
 29         lazya[rt<<1|1]*=lazym[rt];
 30         lazya[rt<<1]+=lazya[rt];
 31         lazya[rt<<1|1]+=lazya[rt];
 32         tree[rt<<1]*=lazym[rt];
 33         tree[rt<<1|1]*=lazym[rt];
 34         tree[rt<<1]+=(len-len/2)*lazya[rt];
 35         tree[rt<<1|1]+=len/2*lazya[rt];
 36         lazya[rt]=0;
 37         lazym[rt]=1;
 38     }
 39 }
 40 
 41 void build(int l,int r,int rt){
 42     lazya[rt]=0;
 43     lazym[rt]=1;
 44     if(l==r){
 45         tree[rt]=0;
 46         return;
 47     }
 48     int mid=(l+r)/2;
 49     build(lson);
 50     build(rson);
 51     pushup(rt);
 52 }
 53 
 54 void mul(int L,int R,ull k,int l,int r,int rt){
 55     if(L<=l&&R>=r){
 56         pushdown(r-l+1,rt);
 57         tree[rt]*=k;
 58         lazym[rt]*=k;
 59         lazya[rt]*=k;
 60         return;
 61     }
 62     int mid=(l+r)/2;
 63     pushdown(r-l+1,rt);
 64     if(L<=mid) mul(L,R,k,lson);
 65     if(R>mid) mul(L,R,k,rson);
 66     pushup(rt);
 67 }
 68 
 69 void add(int L,int R,ull k,int l,int r,int rt){
 70     if(L<=l&&R>=r){
 71         pushdown(r-l+1,rt);
 72         tree[rt]+=(r-l+1)*k;
 73         lazya[rt]+=k;
 74         return;
 75     }
 76     int mid=(l+r)/2;
 77     pushdown(r-l+1,rt);
 78     if(L<=mid) add(L,R,k,lson);
 79     if(R>mid) add(L,R,k,rson);
 80     pushup(rt);
 81 }
 82 
 83 void Not(int L,int R,int l,int r,int rt){
 84     if(L<=l&&R>=r){
 85         pushdown(r-l+1,rt);
 86         tree[rt]+=(r-l+1);
 87         tree[rt]=-tree[rt];
 88         lazym[rt]=-lazym[rt];
 89         lazya[rt]++;
 90         lazya[rt]=-lazya[rt];
 91         return;
 92     }
 93     int mid=(l+r)/2;
 94     pushdown(r-l+1,rt);
 95     if(L<=mid) Not(L,R,lson);
 96     if(R>mid) Not(L,R,rson);
 97     pushup(rt);
 98 }
 99 
100 ull query(int L,int R,int l,int r,int rt){
101     if(L<=l&&R>=r){
102         return tree[rt];
103     }
104     int mid=(l+r)/2;
105     pushdown(r-l+1,rt);
106     ull ans=0;
107     if(L<=mid) ans+=query(L,R,lson);
108     if(R>mid) ans+=query(L,R,rson);
109     pushup(rt);
110     return ans;
111 }
112 
113 void dfs1(int now,int f,int deep){
114     dep[now]=deep;
115     siz[now]=1;
116     fa[now]=f;
117     int maxson=-1;
118     for(int i=0;i<ve[now].size();i++){
119         if(ve[now][i]==f) continue;
120         dfs1(ve[now][i],now,deep+1);
121         siz[now]+=siz[ve[now][i]];
122         if(siz[ve[now][i]]>maxson){
123             maxson=siz[ve[now][i]];
124             son[now]=ve[now][i];
125         }
126     }
127 }
128 
129 void dfs2(int now,int topp){
130     id[now]=++cnt;
131     val[cnt]=v[now];
132     top[now]=topp;
133     if(!son[now]) return;
134     dfs2(son[now],topp);
135     for(int i=0;i<ve[now].size();i++){
136         if(ve[now][i]==son[now]||ve[now][i]==fa[now]) continue;
137         dfs2(ve[now][i],ve[now][i]);
138     }
139 }
140 
141 ull qRange(int x,int y){
142     ull ans=0;
143     while(top[x]!=top[y]){
144         if(dep[top[x]]<dep[top[y]]) swap(x,y);
145         ans+=query(id[top[x]],id[x],1,n,1);
146         x=fa[top[x]];
147     }
148     if(dep[x]>dep[y]) swap(x,y);
149     ans+=query(id[x],id[y],1,n,1);
150     return ans;
151 }
152 
153 void addRange(int x,int y,int k){
154     while(top[x]!=top[y]){
155         if(dep[top[x]]<dep[top[y]]) swap(x,y);
156         add(id[top[x]],id[x],k,1,n,1);
157         x=fa[top[x]];
158     }
159     if(dep[x]>dep[y]) swap(x,y);
160     add(id[x],id[y],k,1,n,1);
161 }
162 
163 void mulRange(int x,int y,int k){
164     while(top[x]!=top[y]){
165         if(dep[top[x]]<dep[top[y]]) swap(x,y);
166         mul(id[top[x]],id[x],k,1,n,1);
167         x=fa[top[x]];
168     }
169     if(dep[x]>dep[y]) swap(x,y);
170     mul(id[x],id[y],k,1,n,1);
171 }
172 
173 void notRange(int x,int y){
174     while(top[x]!=top[y]){
175         if(dep[top[x]]<dep[top[y]]) swap(x,y);
176         Not(id[top[x]],id[x],1,n,1);
177         x=fa[top[x]];
178     }
179     if(dep[x]>dep[y]) swap(x,y);
180     Not(id[x],id[y],1,n,1);
181 }
182 
183 int main(){
184     int m,r;
185     while(~scanf("%d",&n)){
186         memset(v,0,sizeof(v));
187         memset(val,0,sizeof(val));
188         memset(dep,0,sizeof(dep));
189         memset(fa,0,sizeof(fa));
190         memset(siz,0,sizeof(siz));
191         memset(son,0,sizeof(son));
192         memset(id,0,sizeof(id));
193         memset(top,0,sizeof(top));
194         int pos,z,x,y;
195         for(int i=0;i<=n;i++){
196             ve[i].clear();
197         }
198         for(int i=2;i<=n;i++){
199             scanf("%d",&x);
200             ve[x].push_back(i);
201             ve[i].push_back(x);
202         }
203         cnt=0;
204         dfs1(1,0,1);
205         dfs2(1,1);
206         build(1,n,1);
207         scanf("%d",&m);
208         for(int i=1;i<=m;i++){
209             scanf("%d %d %d",&pos,&x,&y);
210             if(pos==1){
211                 scanf("%d",&z);
212                 mulRange(x,y,z);
213             }
214             else if(pos==2){
215                 scanf("%d",&z);
216                 addRange(x,y,z);
217             }
218             else if(pos==3){
219                 notRange(x,y);
220             }
221             else{
222                 printf("%llu\n",qRange(x,y));
223             }
224         }
225     }
226 }