树链剖分学习笔记

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 using namespace std;
  5 const int N = 100001;
  6 int deep[N],fa[N],son[N],size[N],idx[N],cnt,top[N],n,m,r,p,tot,head[N],a[N],b[N];
  7 struct edge
  8 {
  9     int next,to;
 10 } e[N<<1];
 11 struct T
 12 {
 13     int l,r,w,f;
 14 } tree[N<<2];
 15 inline void add(int x,int y)
 16 {
 17     e[++tot].next=head[x];
 18     e[tot].to=y;
 19     head[x]=tot;
 20 }
 21 void comup(int k)
 22 {
 23     tree[k].w=tree[k<<1].w+tree[k<<1|1].w;
 24 }
 25 void dfs1(int x,int f)
 26 {
 27     fa[x]=f;
 28     size[x]=1;
 29     for(int i=head[x]; i!=-1; i=e[i].next)
 30     {
 31         if(!deep[e[i].to] && e[i].to != f)
 32         {
 33             deep[e[i].to]=deep[x]+1;
 34             dfs1(e[i].to,x);
 35             size[x]+=size[e[i].to];
 36             if(size[e[i].to]>size[son[x]]) son[x]=e[i].to;
 37         }
 38     }
 39 }
 40 void dfs2(int x,int topf)
 41 {
 42     idx[x] = ++cnt;
 43     top[x] = topf;
 44     if(!son[x]) return;
 45     dfs2(son[x],topf);
 46     for(int i=head[x]; i!=-1; i=e[i].next)
 47         if(!top[e[i].to]) dfs2(e[i].to,e[i].to);
 48 }
 49 void build(int k,int ll,int rr)
 50 {
 51     tree[k].l=ll,tree[k].r=rr;
 52     if(ll==rr)
 53     {
 54         tree[k].w=a[ll];
 55         return;
 56     }
 57     int m=(ll+rr)>>1;
 58     build(k<<1,ll,m);
 59     build(k<<1|1,m+1,rr);
 60     comup(k);
 61 }
 62 void down(int k)
 63 {
 64     if(tree[k].f)
 65     {
 66         tree[k<<1].f=(tree[k<<1].f+tree[k].f)%p;
 67         tree[k<<1|1].f=(tree[k<<1|1].f+tree[k].f)%p;
 68         tree[k<<1].w=(tree[k<<1].w+(tree[k<<1].r-tree[k<<1].l+1)*tree[k].f)%p;
 69         tree[k<<1|1].w=(tree[k<<1|1].w+(tree[k<<1|1].r-tree[k<<1|1].l+1)*tree[k].f)%p;
 70         tree[k].f=0;
 71     }
 72 }
 73 void add_interval(int k,int ll,int rr,int y)
 74 {
 75     if(tree[k].l>=ll&&tree[k].r<=rr)
 76     {
 77         tree[k].w=(tree[k].w+(tree[k].r-tree[k].l+1)*y)%p;
 78         tree[k].f=(tree[k].f+y)%p;
 79         return;
 80     }
 81     down(k);
 82     int m=(tree[k].l+tree[k].r)>>1;
 83     if(ll<=m) add_interval(k<<1,ll,rr,y);
 84     if(rr>m) add_interval(k<<1|1,ll,rr,y);
 85     comup(k);
 86 }
 87 int asksum_interval(int k,int ll,int rr)
 88 {
 89     int ans=0;
 90     if(tree[k].l>=ll&&tree[k].r<=rr)
 91     {
 92         ans=(ans+tree[k].w)%p;
 93         return ans;
 94     }
 95     down(k);
 96     int m=(tree[k].l+tree[k].r)>>1;
 97     if(ll<=m) ans=(ans+asksum_interval(k<<1,ll,rr))%p;
 98     if(rr>m) ans=(ans+asksum_interval(k<<1|1,ll,rr))%p;
 99     comup(k);
100     return ans;
101 }
102 int asksum_tree(int x,int y)
103 {
104     int ans=0;
105     while(top[x]!=top[y])
106     {
107         if(deep[top[x]]<deep[top[y]]) swap(x,y);
108         ans=(ans+asksum_interval(1,idx[top[x]],idx[x]))%p;
109         x=fa[top[x]];
110     }
111     if(deep[x]<deep[y]) swap(x,y);
112     return (ans+asksum_interval(1,idx[y],idx[x]))%p;
113 }
114 void add_tree(int x,int y,int val)
115 {
116     while(top[x]!=top[y])
117     {
118         if(deep[top[x]]<deep[top[y]]) swap(x,y);
119         add_interval(1,idx[top[x]],idx[x],val);
120         x=fa[top[x]];
121     }
122     if(deep[x]<deep[y]) swap(x,y);
123     add_interval(1,idx[y],idx[x],val);
124 }
125 int main()
126 {
127     memset(head,-1,sizeof(head));
128     cin >> n >> m >> r >> p;
129     for(int i=1; i<=n; i++)cin>>b[i],b[i]=b[i]%p;
130     for(int i=1; i<=n-1; i++)
131     {
132         int a,b;
133         cin >> a >> b;
134         add(a,b);
135         add(b,a);
136     }
137     deep[r]=1;
138     dfs1(r,0);
139     dfs2(r,r);
140     for(int i=1; i<=n; i++)a[idx[i]] = b[i];
141     build(1,1,n);
142     for(int i=1; i<=m; i++)
143     {
144         int flag,x,y,c;
145         cin >> flag;
146         if(flag==1)
147         {
148             cin >> x >> y >> c;
149             add_tree(x,y,c);
150         }
151         if(flag==2)
152         {
153             cin >> x >> y;
154             cout<<asksum_tree(x,y)<<endl;
155         }
156         if(flag==3)
157         {
158             cin >> x >> c;
159             c=c%p;
160             add_interval(1,idx[x],idx[x]+size[x]-1,c);
161         }
162         if(flag==4)
163         {
164             cin >> x;
165             cout<<asksum_interval(1,idx[x],idx[x]+size[x]-1)<<endl;
166         }
167     }
168     return 0;
169 }