小白，自学树剖，样例过，全WA求救

@shangcheng  2019-08-26 11:12 回复
#include <cstdio>
#define int long long
const int maxn = 1e5+5;
inline int re() {
char c;
int w=1;
while((c=getchar())<'0'||c>'9')if(c=='-')w=-1;
int res = c-'0';
while((c=getchar())>='0' && c<='9')res = (res<<3) + (res<<1) + c - '0';
return res * w;
}
inline long long min(long long a,long long b) {
return a<b?a:b;
}
inline void swap(int &x,int &y){
x ^= y,y ^= x,x ^= y;
}
int n,m,r,mod;
struct Edge {
int next,to;
} e[maxn<<1];
inline void add_edge(int x,int y) {
e[tot].to = y;
}
int val[maxn],rank[maxn],fa[maxn],son[maxn],siz[maxn],dep[maxn],tid[maxn],top[maxn],time;
inline void dfs1(int u,int fath) {
int maxson = -1;
dep[u] = dep[fath] + 1;
fa[u] = fath;
siz[u] = 1;
if(v == fath)continue;
dfs1(v,u);
siz[u] += siz[v];
if(siz[v] > maxson)maxson = siz[v],son[u] = v;
}
return ;
}
inline void dfs2(int u,int topf) {
tid[u] = ++time;
rank[time] = u;
top[u] = topf;
if(!son[u])return ;
dfs2(son[u],topf);
if(v == fa[u] || v == son[u])continue;
dfs2(v,v);
}
return ;
}
inline void build(int k,int l,int r){
if(l==r){
sum[k] = val[rank[l]];
return ;
}
int mid = l+r>>1;
build(k<<1,l,mid),build(k<<1|1,mid+1,r);
sum[k] = (sum[k<<1] + sum[k<<1|1])%mod;
return ;
}
inline void Add(int k,int l,int r,int v){
sum[k] = (sum[k] + (r-l+1)*v)%mod;
return ;
}
inline void markdown(int k,int l,int r,int mid){
return ;
}
inline void modify(int k,int l,int r,int x,int y,int v){
if(l>y||r<x)return ;
int mid = l+r>>1;
markdown(k,l,r,mid);
modify(k<<1,l,mid,x,y,v),modify(k<<1|1,mid+1,r,x,y,v);
sum[k] = (sum[k<<1] + sum[k<<1|1])%mod;
return ;
}
inline int query(int k,int l,int r,int x,int y){
if(l>y||r<x)return 0;
if(l>=x&&r<=y)return sum[k];
int mid = l+r>>1;
markdown(k,l,r,mid);
return (query(k<<1,l,mid,x,y)+query(k<<1|1,mid+1,r,x,y))%mod;
}
inline void path_modify(int x,int y,int v){
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]])swap(x,y);
modify(1,1,n,tid[top[x]],tid[x],v);
x = fa[top[x]];
}
if(dep[x] > dep[y])swap(x,y);
modify(1,1,n,tid[x],tid[y],v);
return ;
}
inline int path_query(int x,int y){
int ans = 0;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]])swap(x,y);
ans = (ans+query(1,1,n,tid[top[x]],tid[x]))%mod;
x = fa[top[x]];
}
if(dep[x] > dep[y])swap(x,y);
ans = (ans+query(1,1,n,tid[x],tid[y]))%mod;
return ans;
}
signed main(){
n = re(),m = re(),r = re(),mod = re();
for(int i=1;i<=n;++i)val[i] = re();
dfs1(r,0),dfs2(r,r),build(1,1,n);
for(int i=1,opt,x,y,z;i<=m;++i){
opt = re();
if(opt == 1)x = re(),y = re(),z = re(),path_modify(x,y,z);
if(opt == 2)x = re(),y = re(),printf("%lld\n",path_query(x,y));
if(opt == 3)x = re(),z = re(),modify(1,1,n,tid[x],tid[x]+siz[x]-1,z);
if(opt == 4)x = re(),printf("%lld\n",query(1,1,n,tid[x],tid[x]+siz[x]-1));
}
return 0;
}

求救

@szbszb  2019-08-26 11:23 回复 举报