Xlon_Rainfi @ 2024-03-31 21:18:36
把所有数组空间开大一倍就行了。
很神奇的是当初我做这道题时 #8 #9 #10 MLE，结果我把空间开大一倍反而 A 了，如果有大佬知道为什么可以在讨论区 at 我
by st66 @ 2024-04-06 15:22:15
@wuxinlong 是不是因为树结构的存储是双向的，所以要开两倍空间，我就把链式前向星的数组扩大一倍就过了，其它的都没改。
by Xlon_Rainfi @ 2024-04-06 20:58:34
@st66 哦！懂了。话说我的 MLE 是为啥？
by st66 @ 2024-04-07 09:30:22
@wuxinlong 不知道唉，有无源码看看？
by bitset_iTM @ 2024-04-08 22:07:17
@wuxinlong 可能是越界访问到错误数据（如负数），然后就递归的时候爆栈了？
by Xlon_Rainfi @ 2024-04-09 20:47:15
MLE 代码：
#include <bits/stdc++.h>
#define ll long long
#define tx t[x]
#define lc t[x<<1]
#define rc t[x<<1|1]
#define ls x<<1
#define rs x<<1|1
using namespace std;
const ll N=1e5+10;
struct EDGE{ll to,pre;}e[N];
ll n,m,r,p,head[N],cnt,fa[N],dep[N],son[N],siz[N],top[N],dfn[N],w[N],v[N],tim;
struct Segment_Tree{//线段树
struct node{ll l,r,s,m;}t[N<<2];
inline ll len(ll x){return tx.r-tx.l+1;}
inline void pushup(ll x){tx.s=lc.s+rc.s;}
inline void pushdown(ll x){
lc.m+=tx.m,rc.m+=tx.m;
lc.s+=len(ls)*tx.m,rc.s+=len(rs)*tx.m;
tx.m=0;
}
void build(ll l,ll r,ll x){
// cout<<1;
tx.l=l,tx.r=r;
if(l==r)tx.s=w[l];
else{
ll mid=(r+l)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
pushup(x);
}
}
void add(ll l,ll r,ll x,ll k){//加法
// cout<<2;
if(tx.r<l||r<tx.l)return;
if(l<=tx.l&&tx.r<=r){
tx.m+=k,tx.s+=k*len(x);
return;
}
pushdown(x);
add(l,r,ls,k),add(l,r,rs,k);
pushup(x);
}
ll query(ll l,ll r,ll x){//查询
// cout<<3;
if(tx.r<l||r<tx.l)return 0;
if(l<=tx.l&&tx.r<=r)return tx.s;
pushdown(x);
return query(l,r,ls)+query(l,r,rs);
}
}se_tr;
inline void add_edge(ll from,ll to){//添加边
e[++cnt]=(EDGE){to,head[from]};
head[from]=cnt;
}
void dfs1(ll p,ll f){
// cout<<4;
fa[p]=f;
dep[p]=dep[f]+1;
siz[p]=1;
for(ll i=head[p],mxn=INT_MIN;i;i=e[i].pre){
if(e[i].to==f)continue;
dfs1(e[i].to,p);
siz[p]+=siz[e[i].to];
if(siz[e[i].to]>mxn)mxn=siz[e[i].to],son[p]=e[i].to;
}
}
void dfs2(ll p,ll t){
// cout<<5;
dfn[p]=++tim;
w[tim]=v[p];
top[p]=t;
if(!son[p])return;
dfs2(son[p],t);
for(int i=head[p];i;i=e[i].pre){
if(e[i].to==fa[p]||e[i].to==son[p])continue;
dfs2(e[i].to,e[i].to);
}
}
void add_tree(ll x,ll k){se_tr.add(dfn[x],dfn[x]+siz[x]-1,1,k);}//对子树做加法
ll query_tree(ll x){return se_tr.query(dfn[x],dfn[x]+siz[x]-1,1);}//查询子树
void add_path(ll x,ll y,ll k){//对x->y的路径做加法
while(top[x]!=top[y]){
// cout<<6;
if(dep[top[x]]<dep[top[y]])swap(x,y);
se_tr.add(dfn[top[x]],dfn[x],1,k);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
se_tr.add(dfn[x],dfn[y],1,k);
}
ll query_path(ll x,ll y){//查询x->y的路径
ll ans=0;
while(top[x]!=top[y]){
// cout<<7;
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans+=se_tr.query(dfn[top[x]],dfn[x],1);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans+=se_tr.query(dfn[x],dfn[y],1);
return ans%p;
}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin>>n>>m>>r>>p;
// p=INT_MAX;
for(int i=1;i<=n;i++)cin>>v[i];
for(int i=1;i<=n-1;i++){
ll x,y;
cin>>x>>y;
// cout<<9;
add_edge(x,y);
add_edge(y,x);
}
// cout<<8;
dfs1(r,r),dfs2(r,r),se_tr.build(1,n,1);
while(m--){
ll op,x,y,z;
cin>>op>>x;
if(op==1){
cin>>y>>z;
add_path(x,y,z);
}else if(op==2){
cin>>y;
cout<<query_path(x,y)%p<<endl;
}else if(op==3){
cin>>z;
add_tree(x,z);
}else cout<<query_tree(x)%p<<endl;
}
return 0;
}@st66
by st66 @ 2024-04-15 09:03:06
@wuxinlong 应该是像楼上大佬所说的，数组开太小了，dfs遍历子树时越界访问导致栈溢出了吧
by Xlon_Rainfi @ 2024-04-15 09:30:03
@st66 @bitset_iTM 谢谢大佬
by Nicolas192837 @ 2024-08-08 22:00:09
感谢，但是我是TLE这3个点，想问为啥