题目传送门
解题思路:
树链剖分的板子,写这篇博客只是为了存个代码.
AC代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 5 using namespace std; 6 7 int n,m,rr,p,a[100001],tot,head[100001],rk[100001]; 8 //rk[i]表示dfs中第i个被访问的点是哪个(或者说在线段树上第i号是谁),线段树赋值时有用 9 struct xianduanshu { 10 int v,l,r,lazy; 11 }e[400002]; 12 struct bian { 13 int to,next; 14 }c[200001]; 15 struct dian { 16 int f,d,son,si,top,id; 17 }q[100001]; 18 //父亲,相对于根的深度,重儿子,子树大小,链顶,编号(线段树上的) 19 20 inline void build(int rt,int L,int R) {//线段树建树 21 e[rt].l = L;e[rt].r = R; 22 if(L == R) { 23 e[rt].v = a[rk[L]] % p; 24 return ; 25 } 26 int mid = L + R >> 1; 27 build(rt * 2,L,mid); 28 build(rt * 2 + 1,mid + 1,R); 29 e[rt].v = (e[rt*2].v % p + e[rt*2+1].v % p) % p; 30 } 31 32 inline void add(int x,int y) { 33 c[++tot].to = y; 34 c[tot].next = head[x]; 35 head[x] = tot; 36 } 37 38 inline void dfs1(int u,int fa,int deep) {//找重儿子 39 q[u].d = deep; 40 q[u].f = fa; 41 q[u].si = 1; 42 q[u].son = 0; 43 for(int i = head[u];i; i = c[i].next) { 44 int o = c[i].to; 45 if(o == fa) continue; 46 dfs1(o,u,deep + 1); 47 q[u].si += q[o].si; 48 if(q[q[u].son].si < q[o].si) q[u].son = o; 49 } 50 } 51 52 inline void dfs2(int rt,int topf) {//找重链 53 q[rt].id = ++tot; 54 rk[tot] = rt; 55 q[rt].top = topf; 56 if(q[rt].son == 0) return ; 57 dfs2(q[rt].son,topf);//处理重链 58 for(int i = head[rt];i; i = c[i].next) { 59 int o = c[i].to; 60 if(o == q[rt].f || o == q[rt].son) continue; 61 dfs2(o,o);//处理轻链 62 } 63 } 64 65 inline void pushdown(int rt) { 66 if(e[rt].lazy) { 67 e[rt*2].v = (e[rt*2].v + e[rt].lazy * (e[rt*2].r - e[rt*2].l + 1) % p) % p; 68 e[rt*2+1].v = (e[rt*2+1].v + e[rt].lazy * (e[rt*2+1].r - e[rt*2+1].l + 1) % p) % p; 69 e[rt*2].lazy = (e[rt*2].lazy + e[rt].lazy) % p; 70 e[rt*2+1].lazy = (e[rt*2+1].lazy + e[rt].lazy) % p; 71 e[rt].lazy = 0; 72 } 73 } 74 75 inline void pl(int rt,int L,int R,int vv) { 76 if(L <= e[rt].l && R >= e[rt].r) { 77 e[rt].v = (e[rt].v + vv * (e[rt].r - e[rt].l + 1) % p) % p; 78 e[rt].lazy = (e[rt].lazy + vv) % p; 79 return ; 80 } 81 pushdown(rt); 82 int mid = e[rt].l + e[rt].r >> 1; 83 if(L <= mid) pl(rt * 2,L,R,vv); 84 if(R > mid) pl(rt * 2 + 1,L,R,vv); 85 e[rt].v = (e[rt*2].v % p + e[rt*2+1].v % p) % p; 86 } 87 88 inline void treeadd(int x,int y,int z) {//区间修改 89 int tx = q[x].top; 90 int ty = q[y].top; 91 while(tx != ty) { 92 if(q[tx].d >= q[ty].d) { 93 pl(1,q[tx].id,q[x].id,z); 94 x = q[tx].f;tx = q[x].top; 95 } 96 else { 97 pl(1,q[ty].id,q[y].id,z); 98 y = q[ty].f;ty = q[y].top; 99 } 100 } 101 if(q[x].d > q[y].d) 102 pl(1,q[y].id,q[x].id,z); 103 else 104 pl(1,q[x].id,q[y].id,z); 105 } 106 107 inline int chaxun(int rt,int L,int R) { 108 long long uu = 0; 109 if(e[rt].l >= L && e[rt].r <= R) return e[rt].v % p; 110 pushdown(rt); 111 int mid = e[rt].l + e[rt].r >> 1; 112 if(L <= mid) uu += chaxun(rt * 2,L,R),uu %= p; 113 if(R > mid) uu += chaxun(rt * 2 + 1,L,R), uu %= p; 114 return uu % p; 115 } 116 117 inline int treesum(int x,int y) {//查询 118 long long ans = 0; 119 int tx = q[x].top; 120 int ty = q[y].top; 121 while(tx != ty) { 122 if(q[tx].d >= q[ty].d) { 123 ans += chaxun(1,q[tx].id,q[x].id); 124 ans %= p; 125 x = q[tx].f;tx = q[x].top; 126 } 127 else { 128 ans += chaxun(1,q[ty].id,q[y].id); 129 ans %= p; 130 y = q[ty].f;ty = q[y].top; 131 } 132 } 133 if(q[x].d > q[y].d) 134 ans += chaxun(1,q[y].id,q[x].id),ans %= p; 135 else 136 ans += chaxun(1,q[x].id,q[y].id),ans %= p; 137 return ans % p; 138 } 139 140 int main() { 141 scanf("%d%d%d%d",&n,&m,&rr,&p); 142 for(int i = 1;i <= n; i++) 143 scanf("%d",&a[i]); 144 for(int i = 1;i < n; i++) { 145 int x,y; 146 scanf("%d%d",&x,&y); 147 add(x,y); 148 add(y,x); 149 } 150 dfs1(rr,0,1); 151 tot = 0; 152 dfs2(rr,rr); 153 build(1,1,n); 154 for(int i = 1;i <= m; i++) { 155 int x,y,z,ww; 156 scanf("%d",&ww); 157 if(ww == 1) { 158 scanf("%d%d%d",&x,&y,&z); 159 treeadd(x,y,z % p); 160 } 161 if(ww == 2) { 162 scanf("%d%d",&x,&y); 163 int aa = 0; 164 aa = treesum(x,y); 165 printf("%d ",aa % p); 166 } 167 if(ww == 3) { 168 scanf("%d%d",&x,&y); 169 pl(1,q[x].id,q[x].id + q[x].si - 1,y % p); 170 } 171 if(ww == 4) { 172 scanf("%d",&x); 173 printf("%d ",chaxun(1,q[x].id,q[x].id + q[x].si - 1) % p); 174 } 175 } 176 return 0; 177 }