本文共 6814 字，大约阅读时间需要 22 分钟。
落谷3384
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 using namespace std; 12 typedef long long LL; 13 const double pi=acos(-1.0); 14 const double e=exp(1); 15 //const int MAXN =2e5+10; 16 const LL N = 100010*4; 17 18 struct node 19 { 20 LL l,r; 21 LL mid() { 22 return (l + r) / 2; 23 } 24 }node[N]; 25 LL sum[N]; 26 LL add[N]; 27 28 LL con[N]; 29 LL head[N]; 30 struct edge{ 31 LL to; 32 LL next; 33 LL w; 34 }edge[N]; 35 36 37 LL f[N]; //结点i的父结点 38 LL d[N]; // 结点i的深度 39 LL size[N]; // 结点i子树的规模(结点数) 40 LL son[N]; // 结点i的重结点 41 LL top[N]; // 结点i所在链的顶端结点 42 LL id[N]; // 树中结点剖分后对应的数组下标 43 LL rk[N]; // 剖分后数组下标对应的树上的结点 44 45 LL cnt1 = 1, cnt = 0; 46 LL n,m,r,p; 47 48 void PushUp(LL i) 49 { 50 //sum[i] = max(sum[i << 1], sum[i << 1 | 1]); 51 sum[i] = sum[i << 1] + sum[i << 1 | 1]; 52 } 53 54 void PushDown(LL i,LL L) // LΪÇøŒä³€¶È £šÑÓ³Ù±êŒÇ£© 55 { 56 if(add[i]) 57 { 58 add[i << 1] += add[i] % p; 59 add[i << 1 | 1] += add[i] % p; 60 sum[i << 1] += add[i] * (L - (L >> 1)) % p; // Ò׎í 61 sum[i << 1 | 1] += add[i] * (L >> 1) % p; 62 add[i] = 0; 63 } 64 } 65 66 void Build(LL l, LL r, LL i) 67 { 68 //cout << " l: " << l << " r: " << r << endl; 69 node[i].l = l; 70 node[i].r = r; 71 sum[i] = 0; 72 add[i] = 0; 73 if(l == r) 74 { 75 // cout << " l: " << l << " r: " << r << " " << rk[cnt1] << endl; 76 sum[i] = con[rk[cnt1++]]; 77 return ; 78 //scanf("%d",&sum[i]); 79 } 80 LL m = node[i].mid(); 81 82 Build(l, m, i << 1); 83 Build(m+1, r, i << 1 | 1); 84 85 PushUp(i); 86 } 87 88 LL Query(LL l, LL r, LL i) 89 { 90 if(node[i].l == l && node[i].r == r) 91 { 92 return sum[i]; 93 } 94 PushDown(i, node[i].r - node[i].l + 1); 95 LL m = node[i].mid(); 96 LL ans = 0; 97 if(r <= m) 98 { 99 ans += Query(l, r, i << 1) % p;100 }101 else102 {103 if(l > m)104 {105 ans += Query(l, r, i << 1 | 1) % p;106 }107 else108 {109 ans += Query(l, m, i << 1) % p;110 ans += Query(m+1, r, i << 1 | 1) % p;111 }112 }113 return ans;114 }115 116 void Update(LL l, LL r, LL x, LL i)117 {118 // cout << " ^^ " << node[i].l << " " << node[i].r << endl;119 if(node[i].l == l && node[i].r == r)120 {121 sum[i] += x * (r - l + 1) % p;122 add[i] += x % p;123 return ;124 }125 PushDown(i,node[i].r - node[i].l + 1);126 LL m = node[i].mid();127 if(r <= m)128 {129 Update(l, r, x, i << 1);130 }131 else132 {133 if(l > m)134 {135 Update(l, r, x, i << 1 | 1);136 }137 else138 {139 Update(l, m, x, i << 1);140 Update(m+1, r, x, i << 1 | 1);141 }142 }143 PushUp(i);144 }145 146 147 148 // 处理size,son,f,d数组149 void dfs1(LL u, LL fa, LL depth) //当前节点、父节点、层次深度150 {151 LL i;152 f[u] = fa;153 d[u] = depth;154 size[u] = 1; //这个点本身size = 1;155 156 for( i = head[u]; i != -1; i = edge[i].next)157 {158 LL v = edge[i].to;159 if(v == fa)160 continue;161 dfs1(v, u, depth + 1);162 size[u] += size[v];163 if(size[v] > size[son[u]]) //son[u]数组为u的重儿子164 {165 son[u] = v; 166 }167 }168 }169 //dfs1(root, 0, 1); // 处理结点子树的规模，每个结点的重儿子，结点所在的深度170 171 172 173 // 处理top,id,rk数组174 void dfs2(LL u, LL t) //当前结点、重链顶端175 {176 top[u] = t;177 id[u] = ++cnt; //标记dfs序178 rk[cnt] = u; // 序号cnt对应结点u179 if(!son[u]) // 当点u为叶子节点时，代表一条重链剖分完毕。180 return ; // 返回到倒数第二个结点，从该结点出发，剖分另一条链。181 dfs2(son[u],t); 182 183 for(LL i = head[u]; i != -1; i = edge[i].next) //从该结点所连接的结点出发，进行剖分184 {185 LL v = edge[i].to;186 if(v != son[u] && v != f[u]) // 链头要求不能是结点u的重儿子(因为该结点已经被重链占用了)187 // 也不能是结点u的父结点188 dfs2(v,v); //每条链都是以轻结点为开头，后面链的都是重儿子。所以结点v的链头是它本身。189 } 190 191 }192 193 void U_xy(LL x, LL y, LL z)194 {195 LL ans = 0, fx = top[x], fy = top[y];196 while(fx != fy)197 {198 if(d[fx] >= d[fy])199 {200 if(id[x] <= id[fx])201 Update(id[x], id[fx], z, 1);202 else203 {204 Update(id[fx], id[x], z, 1);205 }206 207 x = f[fx];208 fx = top[x];209 }210 else211 {212 if(id[y] <= id[fy])213 Update(id[y], id[fy], z, 1);214 else215 {216 Update(id[fy], id[y], z, 1);217 }218 219 y = f[fy];220 fy = top[y];221 }222 }223 224 if(id[x] <= id[y])225 {226 Update(id[x], id[y], z, 1);227 }228 else229 {230 Update(id[y], id[x], z, 1);231 }232 233 }234 235 LL Q_xy(LL x, LL y)236 {237 LL ans = 0, fx = top[x], fy = top[y]; //fx代表x的链头结点，fy同理。238 while(fx != fy)239 {240 // cout << " ^^ " << "x: " << x << " y: " << y << "fx: " << fx << "fy: " << fy << endl;241 // cout << id[x] << " " << id[fx] << " ** " << endl;242 if(d[fx] >= d[fy]) // 如果x的深度比y的深度大，所以应让x向上跳243 {244 if(id[x] <= id[fx])245 ans += Query(id[x], id[fx], 1) % p; // 因为剖分后每条链上的结点都是线性存储的，所以x到x链头的父节点的距离，为两者之间的距离的差。246 else247 {248 ans += Query(id[fx], id[x], 1) % p;249 }250 251 x = f[fx]; // x更新为x链头结点的父节点252 fx = top[x]; // fx更新为新x结点的链头结点， 然后再去和fy比较，判断x，y是否在同一条链上了。253 }254 else255 {256 if(id[y] <= id[fy])257 ans += Query(id[y], id[fy], 1) % p;258 else259 {260 ans += Query(id[fy], id[y], 1) % p;261 }262 263 y = f[fy];264 fy = top[y];265 }266 }267 268 if(id[x] <= id[y])269 {270 ans += Query(id[x], id[y], 1) % p;271 }272 else273 {274 ans += Query(id[y], id[x], 1) % p;275 }276 277 return ans % p;278 }279 280 void U_x(LL x, LL z)281 {282 // cout << "id[x]: " << id[x] << " size: " << size[x] << endl;283 // cout << " ** " << Query(id[x],id[x] + size[x] - 1,1) << endl;; 284 Update(id[x], id[x] + size[x] - 1, z, 1);285 // cout << " ** " << Query(id[x],id[x] + size[x] - 1,1) << endl;;286 287 }288 289 LL Q_x(LL x)290 {291 return Query(id[x], id[x] + size[x] - 1, 1) % p;292 }293 294 295 int main()296 {297 298 LL i,j,a,b,x,y,z;299 300 scanf("%lld%lld%lld%lld",&n,&m,&r,&p);301 for(i = 1; i <= n; i ++)302 {303 scanf("%lld",&con[i]);304 }305 306 memset(head,-1,sizeof(head));307 LL cnt2 = 0;308 for(i = 1; i < n; i++)309 {310 scanf("%lld%lld",&a,&b);311 edge[cnt2].to = b;312 edge[cnt2].next= head[a];313 head[a] = cnt2 ++;314 315 316 edge[cnt2].to = a;317 edge[cnt2].next = head[b];318 head[b] = cnt2 ++;319 }320 dfs1(r, 0, 1);321 dfs2(r, r);322 323 324 Build(1, n, 1);325 326 /* 327 cout << "** ";328 for(i = 1; i <= cnt; i++)329 {330 cout << rk[i] << " " ;331 }332 cout << endl;333 */334 while(m--)335 {336 scanf("%lld",&j);337 // cout << "j: " << j << endl;338 if(j == 1)339 {340 scanf("%lld%lld%lld",&x,&y,&z);341 U_xy(x,y,z);342 }343 else if(j == 2)344 {345 scanf("%lld%lld",&x,&y);346 printf("%lld\n", Q_xy(x,y) % p);347 }348 else if(j == 3)349 {350 scanf("%lld%lld",&x,&z);351 U_x(x,z);352 }353 else if(j == 4)354 {355 scanf("%lld",&x);356 printf("%lld\n", Q_x(x) % p);357 }358 }359 return 0;360 }361 362 363 364 365 366 367 368 369 /* 370 888888888888888888888888888 36375 68190 63528 ** 371 888888888888888888888888888 66907 32530 32528 ** 372 373 374 888888888888888888888888888 36375 31713 68190 63528 ** 375 888888888888888888888888888 66907 86992 32530 32528 ** 376 377 */
转载于:https://www.cnblogs.com/daybreaking/p/11312951.html