树链剖分

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <time.h>
  6 #include <string>
  7 #include <set>
  8 #include <map>
  9 #include <list>
 10 #include <stack>
 11 #include <queue>
 12 #include <vector>
 13 #include <bitset>
 14 #include <ext/rope>
 15 #include <algorithm>
 16 #include <iostream>
 17 using namespace std;
 18 #define ll long long
 19 #define minv 1e-6
 20 #define inf 1e9
 21 #define pi 3.1415926536
 22 #define nl 2.7182818284
 23 //const ll mod=1e9+7;//998244353
 24 const int maxn=1e5+10;
 25 
 26 struct node
 27 {
 28     int d;
 29     node *next;
 30 }*e[maxn];
 31 
 32 ll mod,tag[maxn<<2],sum[maxn<<2];
 33 int dep[maxn],siz[maxn],fa[maxn]={0},son[maxn],id[maxn],top[maxn],num=0,n;
 34 bool vis[maxn]={0};
 35 ll v[maxn],point_num=0,old_id[maxn];
 36 
 37 void dfs1(int d,int deep)
 38 {
 39     node *p=e[d];
 40     int maxson=0,dd;
 41     vis[d]=1;
 42     dep[d]=deep;
 43     siz[d]=1;
 44     while (p)
 45     {
 46         dd=p->d;
 47         if (!vis[dd])
 48         {
 49             fa[dd]=d;
 50             dfs1(dd,deep+1);
 51             siz[d]+=siz[dd];
 52             if (siz[dd]>maxson)
 53                 son[d]=dd,maxson=siz[dd];
 54         }
 55         p=p->next;
 56     }
 57 }
 58 
 59 void dfs2(int d,int topd)
 60 {
 61     id[d]=++num;
 62     top[d]=topd;
 63     old_id[num]=d;
 64     if (son[d]!=0)
 65     {
 66         dfs2(son[d],topd);
 67         node *p=e[d];
 68         int dd;
 69         while (p)
 70         {
 71             dd=p->d;
 72             if (dd!=fa[d] && dd!=son[d])
 73                 dfs2(dd,dd);
 74             p=p->next;
 75         }
 76     }
 77 }
 78 
 79 void build(int index,int l,int r)
 80 {
 81     tag[index]=0;
 82     if (l==r)
 83     {
 84 //        scanf("%lld",&sum[index]);
 85         sum[index]=v[old_id[++point_num]];
 86 //        sum[index]=sum[index]%mod;
 87     }
 88     else
 89     {
 90         int m=(l+r)>>1;
 91         build(index<<1,l,m);
 92         build(index<<1|1,m+1,r);
 93         sum[index]=(sum[index<<1]+sum[index<<1|1])%mod;
 94     }
 95 }
 96 
 97 void push_down(int index,int len)
 98 {
 99     tag[index<<1]=(tag[index]+tag[index<<1])%mod;
100     tag[index<<1|1]=(tag[index]+tag[index<<1|1])%mod;
101     sum[index<<1]=(tag[index]*((len+1)>>1)+sum[index<<1])%mod;
102     sum[index<<1|1]=(tag[index]*(len>>1)+sum[index<<1|1])%mod;
103     tag[index]=0;
104 }
105 
106 void update(int index,int l,int r,int x,int y,ll k)
107 {
108     if (x<=l && r<=y)
109     {
110         sum[index]=(k*(r-l+1)+sum[index])%mod;
111         tag[index]=(k+tag[index])%mod;
112         return;
113     }
114     if (tag[index]!=0)
115         push_down(index,r-l+1);
116     int m=(l+r)>>1;
117     if (x<=m)
118         update(index<<1,l,m,x,y,k);
119     if (m<y)
120         update(index<<1|1,m+1,r,x,y,k);
121     sum[index]=(sum[index<<1]+sum[index<<1|1])%mod;
122 }
123 
124 ll query(int index,int l,int r,int x,int y)
125 {
126     if (x<=l && r<=y)
127         return sum[index];
128     if (r<x || l>y)
129         return 0;
130     if (tag[index]!=0)
131         push_down(index,r-l+1);
132     int m=(l+r)>>1;
133     return (query(index<<1,l,m,x,y)+query(index<<1|1,m+1,r,x,y))%mod;
134 }
135 
136 void work1(int x,int y,ll k)
137 {
138     while (top[x]!=top[y])
139     {
140         if (dep[top[x]]<dep[top[y]])
141             swap(x,y);
142         update(1,1,n,id[top[x]],id[x],k);
143         x=fa[top[x]];
144     }
145     if (dep[x]<dep[y])
146         swap(x,y);
147     update(1,1,n,id[y],id[x],k);
148 }
149 
150 ll work2(int x,int y)
151 {
152     ll tot=0;
153     while (top[x]!=top[y])
154     {
155         if (dep[top[x]]<dep[top[y]])    ///top!
156             swap(x,y);
157         tot=(tot+query(1,1,n,id[top[x]],id[x]))%mod;
158         x=fa[top[x]];
159     }
160     if (dep[x]<dep[y])
161         swap(x,y);
162     tot=(tot+query(1,1,n,id[y],id[x]))%mod;
163     return tot;
164 }
165 
166 void work3(int x,ll k)
167 {
168     update(1,1,n,id[x],id[x]+siz[x]-1,k);
169 }
170 
171 ll work4(int x)
172 {
173     return query(1,1,n,id[x],id[x]+siz[x]-1);
174 }
175 
176 int main()
177 {
178     node *p;
179     int q,root,x,y,mode,i;
180     ll k;
181     scanf("%d%d%d%lld",&n,&q,&root,&mod);
182     for (i=1;i<=n;i++)
183         scanf("%lld",&v[i]);
184     for (i=1;i<n;i++)
185     {
186         scanf("%d%d",&x,&y);
187         p=(node*) malloc (sizeof(node));
188         p->d=y;
189         p->next=e[x];
190         e[x]=p;
191 
192         p=(node*) malloc (sizeof(node));
193         p->d=x;
194         p->next=e[y];
195         e[y]=p;
196     }
197 
198     dfs1(root,0);
199     dfs2(root,root);    ///two root
200     build(1,1,n);
201 
202     while (q--)
203     {
204         scanf("%d",&mode);
205         if (mode==1)
206         {
207             scanf("%d%d%lld",&x,&y,&k);
208             work1(x,y,k);
209         }
210         else if (mode==2)
211         {
212             scanf("%d%d",&x,&y);
213             printf("%lld
",work2(x,y));
214         }
215         else if (mode==3)
216         {
217             scanf("%d%lld",&x,&k);
218             work3(x,k);
219         }
220         else
221         {
222             scanf("%d",&x);
223             printf("%lld
",work4(x));
224         }
225     }
226     return 0;
227 }
228 /*
229 5 100 2 10000000
230 0 0 0 0 0
231 1 2
232 1 5
233 3 1
234 4 1
235 1 5 4 1
236 1 2 5 1
237 2 4 5
238 */