@[_Alexande_](/user/363006) 换成分块
by Cocoly1990 @ 2022-05-25 14:09:24
OK。
by wangyibo201026 @ 2022-05-25 14:10:35
完结
by wangyibo201026 @ 2022-05-25 14:10:48
@[Cocoly1990](/user/183026) 我用分块写还是 MLE 了。
by wangyibo201026 @ 2022-05-25 14:29:17
@[_Alexande_](/user/363006) 那你最后咋解决的？是爆栈了吗
by Cocoly1990 @ 2022-05-25 14:33:43
@[Cocoly1990](/user/183026) 我还没有解决。
丑陋的代码：
```cpp
#include<bits/stdc++.h>
#define endl '\n';
#define int long long
using namespace std;
const int N = 1e5 + 1;
const int M = 1e3 + 5;
int n , m, r, p;
int a[N], b[N];
int pos[N], L[M], R[M], sum[M], tag[M];
void update(int lt, int rt, int val){
int x = pos[lt], y = pos[rt];
if(x == y){
for(int i = lt; i <= rt; i++){
b[i] += val;
b[i] %= p;
}
sum[x] += (rt - lt + 1) % p * val % p;
}
else{
for(int i = lt; i <= R[x]; i++){
b[i] += val;
b[i] %= p;
}
sum[x] += (R[x] - lt + 1) % p * val % p;
for(int i = x + 1; i < y; i++){
tag[i] += val;
tag[i] %= p;
}
for(int i = L[y]; i <= rt; i++){
b[i] += val;
b[i] %= p;
}
sum[y] += (rt - L[y] + 1) % p * val % p;
}
}
int query(int lt, int rt){
int ans = 0;
int x = pos[lt], y = pos[rt];
if(x == y){
for(int i = lt; i <= rt; i++){
ans += b[i];
ans += tag[x];
ans %= p;
}
ans %= p;
}
else{
for(int i = lt; i <= R[x]; i++){
ans += b[i];
ans %= p;
ans += tag[x];
ans %= p;
}
ans %= p;
for(int i = x + 1; i < y; i++){
ans += sum[i];
ans %= p;
ans += (R[i] - L[i] + 1) % p * tag[i] % p;
ans %= p;
}
ans %= p;
for(int i = L[y]; i <= rt; i++){
ans += b[i];
ans %= p;
ans += tag[y];
ans %= p;
}
ans %= p;
}
return ans % p;
}
int head[N], tot;
struct Node{
int to, next;
}edges[N];
void add(int u, int v){
tot++;
edges[tot].to = v;
edges[tot].next = head[u];
head[u] = tot;
}
int dep[N], size[N], son[N], fa[N], top[N], id[N];
int cnt;
void dfs1(int x, int f){
fa[x] = f;
size[x] = 1;
dep[x] = dep[f] + 1;
int maxi = -1e9;
for(int i = head[x]; i; i = edges[i].next){
if(edges[i].to != f){
dfs1(edges[i].to, x);
size[x] += size[edges[i].to];
if(size[edges[i].to] > maxi){
maxi = size[edges[i].to];
son[x] = edges[i].to;
}
}
}
}
void dfs2(int x, int t){
top[x] = t;
id[x] = ++cnt;
if(a[x]){
update(id[x], id[x], a[x]);
}
if(!son[x]){
return ;
}
dfs2(son[x], t);
for(int i = head[x]; i; i = edges[i].next){
if(edges[i].to != son[x] && edges[i].to != fa[x]){
dfs2(edges[i].to, edges[i].to);
}
}
}
void Update1(int x, int y, int val){
val %= p;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]]){
swap(x, y);
}
update(id[top[x]], id[x], val);
x = fa[top[x]];
}
if(dep[x] > dep[y]){
swap(x, y);
}
update(id[x], id[y], val);
}
int Query1(int x, int y){
int ans = 0;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]]){
swap(x, y);
}
ans += query(id[top[x]], id[x]);
ans %= p;
x = fa[top[x]];
}
if(dep[x] > dep[y]){
swap(x, y);
}
ans += query(id[x], id[y]);
return ans % p;
}
void Update2(int x, int val){
val %= p;
update(id[x], id[x] + size[x] - 1, val);
}
int Query2(int x){
return query(id[x], id[x] + size[x] - 1);
}
void Solve(){
cin >> n >> m >> r >> p;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
int sq = sqrt(n);
for(int i = 1; i <= sq; i++){
L[i] = (i - 1) * sq + 1;
R[i] = i * sq;
}
R[sq] = n;
for(int i = 1; i <= sq; i++){
for(int j = L[i]; j <= R[i]; j++){
sum[i] = 0;
pos[j] = i;
}
}
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs1(r, 0);
dfs2(r, r);
while(m--){
int op;
cin >> op;
if(op == 1){
int x, y, k;
cin >> x >> y >> k;
Update1(x, y, k);
}
else if(op == 2){
int x, y;
cin >> x >> y;
cout << Query1(x, y) % p << endl;
}
else if(op == 3){
int x, k;
cin >> x >> k;
Update2(x, k);
}
else{
int x;
cin >> x;
cout << Query2(x) % p << endl;
}
}
}
signed main(){
Solve();
return 0;
}
```
by wangyibo201026 @ 2022-05-25 14:35:47
应该不是真的MLE
by jockbutt @ 2022-05-25 15:10:08