@[Ted_hjl](/user/342868) 算了一下，$O(n \sqrt n \log n)$ 是过不了的吧，建议线段树 $O(n \log^2n)$写。
by xinggancaixukun @ 2022-06-02 13:21:15
蒟蒻不会分块，先跑了（
by xinggancaixukun @ 2022-06-02 13:21:51
复杂度 $\mathcal{O}(n\sqrt{n}\log n)$，$n=10^5$ 时 $n\sqrt{n}\log n>79\times 10^7$
by Iwara_qwq @ 2022-06-02 13:28:37
建议线段树
by Iwara_qwq @ 2022-06-02 13:28:54
线段树这玩意不比分块好写？（
by xinggancaixukun @ 2022-06-02 14:04:41
```cpp#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=100005;
int n,m,rt,mod;
int a[MAXN];
namespace segtree
{
int tr[MAXN<<2],tag[MAXN<<2];
inline void P(int p,int l,int r,int k)
{
tr[p]=(tr[p]+(r-l+1)*k)%mod;
tag[p]=(tag[p]+k)%mod;
}
void push_down(int p,int l,int r)
{
int mid=(l+r)>>1;
P(p<<1,l,mid,tag[p]);
P(p<<1|1,mid+1,r,tag[p]);
tag[p]=0;
}
void build(int p,int l,int r)
{
if(l==r)
{
tr[p]=a[l];
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
tr[p]=(tr[p<<1]+tr[p<<1|1])%mod;
}
void add(int p,int st,int en,int l,int r,int k)
{
if(st<=l && r<=en)
{
tr[p]=(tr[p]+(r-l+1)*k)%mod;
tag[p]=(tag[p]+k)%mod;
return;
}
push_down(p,l,r);
int mid=(l+r)>>1;
if(mid>=st) add(p<<1,st,en,l,mid,k);
if(mid+1<=en) add(p<<1|1,st,en,mid+1,r,k);
tr[p]=(tr[p<<1]+tr[p<<1|1])%mod;
}
int query(int p,int st,int en,int l,int r)
{
if(st<=l && r<=en) return tr[p];
push_down(p,l,r);
int mid=(l+r)>>1,ans=0;
if(mid>=st) ans=(ans+query(p<<1,st,en,l,mid))%mod;
if(mid+1<=en) ans=(ans+query(p<<1|1,st,en,mid+1,r))%mod;
return ans;
}
}
using namespace segtree;
namespace sp
{
struct Node
{
int sze,fa,dfn,dep,top,hson;
}b[MAXN];
struct Edge
{
int v,w;
};
vector<Edge> E[MAXN];
void dfs1(int u,int fa)
{
b[u].fa=fa;
b[u].hson=0;
b[u].sze=1;
b[u].dep=b[fa].dep+1;
b[b[u].hson].sze=0;
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i].v,w=E[u][i].w;
if(v==fa) continue;
dfs1(v,u);
b[u].sze+=b[v].sze;
if(b[v].sze>b[b[u].hson].sze)
b[u].hson=v;
}
}
int tot=0,fbk[MAXN];
void dfs2(int u,int fa,int tp)
{
b[u].dfn=++tot; b[u].top=tp; fbk[tot]=u;
if(b[u].hson) dfs2(b[u].hson,u,tp);
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i].v,w=E[u][i].w;
if(v==fa || v==b[u].hson) continue;
dfs2(v,u,v);
}
}
void path_add(int u,int v,int w)
{
while(b[u].top!=b[v].top)
{
if(b[b[u].top].dep<b[b[v].top].dep) swap(u,v);
add(1,b[b[u].top].dfn,b[u].dfn,1,n,w);
u=b[b[u].top].fa;
}
if(b[u].dfn>b[v].dfn) swap(u,v);
add(1,b[u].dfn,b[v].dfn,1,n,w);
}
int path_sum(int u,int v)
{
int ans=0;
while(b[u].top!=b[v].top)
{
if(b[b[u].top].dep<b[b[v].top].dep) swap(u,v);
ans=(ans+query(1,b[b[u].top].dfn,b[u].dfn,1,n))%mod;
u=b[b[u].top].fa;
}
if(b[u].dfn>b[v].dfn) swap(u,v);
return (ans+query(1,b[u].dfn,b[v].dfn,1,n))%mod;
}
void subt_add(int u,int w){add(1,b[u].dfn,b[u].dfn+b[u].sze-1,1,n,w);}
int subt_sum(int u){return query(1,b[u].dfn,b[u].dfn+b[u].sze-1,1,n);}
}
using namespace sp;
int o[MAXN];
signed main()
{
scanf("%lld%lld%lld%lld",&n,&m,&rt,&mod);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<n;i++)
{
int x,y; scanf("%lld%lld",&x,&y);
E[x].push_back((Edge){y,0});
E[y].push_back((Edge){x,0});
}
dfs1(rt,0); dfs2(rt,0,rt);
for(int i=1;i<=n;i++) o[b[i].dfn]=a[i];
for(int i=1;i<=n;i++) a[i]=o[i];
build(1,1,n);
while(m--)
{
int op,x,y,z; scanf("%lld",&op);
if(op==1)
{
scanf("%lld%lld%lld",&x,&y,&z);
path_add(x,y,z);
}
else if(op==2)
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",path_sum(x,y));
}
else if(op==3)
{
scanf("%lld%lld",&x,&z);
subt_add(x,z);
}
else
{
scanf("%lld",&x);
printf("%lld\n",subt_sum(x));
}
}
return 0;
}
```
by xinggancaixukun @ 2022-06-02 14:05:24
@[Ted_hjl](/user/342868) 我想你一定是第一次写树剖吧，写出这么多神奇错误来（这份代码中含有 `//!`）的行是你的错误，自己对着你的代码想吧。（可以忽略其它注释）
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, sq, r, p;
long long w[100005];
vector<int> G[100005];
int dep[100005], fa[100005], son[100005], siz[100005];
int in[100005], out[100005], times, top[100005];
long long wt[100005];
int st[1005], ed[1005], block[100005];
long long ad[1005], sum[1005], res;
void dfs1(int u, int f, int deep)
{
dep[u] = deep;
fa[u] = f;
siz[u] = 1;
int maxson = -1;
for (int i = 0 ; i < G[u].size() ; i ++)
{
int v = G[u][i];
if (v != f)
{
dfs1(v, u, deep + 1);
siz[u] += siz[v];
if (maxson < siz[v])
{
son[u] = v;
maxson = siz[v];
}
}
}
}
void dfs2(int u, int topf)
{
in[u] = ++ times/*,cout<<u<<' '<<times<<"*\n"*/;
top[u] = topf;
wt[times] = w[u];
if (!son[u])
{
out[u] = times;//!
return ;
}
dfs2(son[u], topf);//!
for (int i = 0 ; i < G[u].size() ; i ++)
{
int v = G[u][i];
if (v != fa[u] && v != son[u])
{
dfs2(v, v);//!
}
}
out[u] = times;
}
void add(int l, int r, int k)
{
// cout<<l<<' '<<r<<' '<<k<<"#\n";
int lb = block[l], rb = block[r];
if (lb == rb)
{
for (int i = l ; i <= r ; i ++)
{
wt[i] += k;
sum[lb] += k;
wt[i] %= p;
sum[lb] %= p;
}
return ;
}
for (int i = l ; i <= ed[lb] ; i ++)
{
wt[i] += k;
sum[lb] += k;
wt[i] %= p;//!
sum[lb] %= p;
}
for (int i = st[rb] ; i <= r ; i ++)
{
wt[i] += k;
sum[rb] += k;
wt[i] %= p;
sum[rb] %= p;
}
for (int i = lb + 1 ; i <= rb - 1 ; i ++)
{
ad[i] += k;
ad[i] %= p;
}
}
long long query(int l, int r)
{
// cout<<l<<' '<<r<<' ';
int lb = block[l], rb = block[r];
long long ans = 0;
if (lb == rb)
{
for (int i = l ; i <= r ; i ++)
{
ans += wt[i] + ad[lb];
ans %= p;
}
return /*cout<<ans<<"$\n",*/ans;
}
for (int i = l ; i <= ed[lb] ; i ++)
{
ans += wt[i] + ad[lb];
ans %= p;
}
for (int i = st[rb] ; i <= r ; i ++)
{
ans += wt[i] + ad[rb];
ans %= p;
}
for (int i = lb + 1 ; i <= rb - 1 ; i ++)
{
ans += sum[i] % p + ad[i] * (ed[i] - st[i] + 1) % p;
ans %= p;//!
}
return /*cout<<ans<<"$\n",*/ans;
}
void change1(int l, int r, int k)
{
k %= p;
while (top[l] != top[r])
{
if(dep[top[l]] < dep[top[r]])
{
swap(l, r);
}
add(in[top[l]], in[l], k);
l = fa[top[l]];
}
if (dep[l] > dep[r])
{
swap(l, r);
}
add(in[l], in[r], k);
}
int change2(int l, int r)
{
int ans = 0;
while (top[l] != top[r])
{
if (dep[top[l]] < dep[top[r]])
{
swap(l, r);
}
ans += query(in[top[l]], in[l]);
ans %= p;
l = fa[top[l]];
}
if(dep[l] > dep[r])
{
swap(l, r);
}
ans += query(in[l], in[r]);
return ans % p;
}
int main()
{
cin >> n >> m >> r >> p;
for (int i = 1 ; i <= n ; i ++)
{
cin >> w[i];
}
for (int i = 1 ; i < n ; i ++)
{
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs1(r, 0, 1);
dfs2(r, r);
sq = sqrt(n);
for (int i = 1 ; i <= n ; i ++)
{
int s = i / sq + 1;
if (!st[s])
{
st[s] = i;
}
ed[s] = i;
block[i] = s;
sum[s] += wt[i];
sum[s] %= p;
}
while (m --)
{
int opt;
cin >> opt;
if (opt == 1)
{
int x, y, z;
cin >> x >> y >> z;
change1(x, y, z);
}
else if (opt == 2)
{
int x, y;
cin >> x >> y;
cout << change2(x, y) << endl;
}
else if (opt == 3)
{
int x, z;
cin >> x >> z;
add(in[x], out[x], z%p);
}
else
{
int x;
cin >> x;
cout << query(in[x], out[x]) << endl;
}
// for(int i=1;i<=n;i++)cout<<wt[i]+ad[block[i]]<<" \n"[i==n];
}
return 0;
}
```
by abruce @ 2022-06-02 16:06:06
@[abruce](/user/104324) %%%，感谢
by qfpjm @ 2022-06-02 17:33:37