小白,自学树剖,样例过,全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;
int head[maxn],tot;
struct Edge {
    int next,to;
} e[maxn<<1];
inline void add_edge(int x,int y) {
    e[++tot].next = head[x];
    e[tot].to = y;
    head[x] = tot;
}
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;
    for(int i=head[u],v; v=e[i].to,i; i=e[i].next) {
        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);
    for(int i=head[u],v; v=e[i].to,i; i=e[i].next) {
        if(v == fa[u] || v == son[u])continue;
        dfs2(v,v);
    }
    return ;
}
int sum[maxn<<2],add[maxn<<2];
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;
    add[k] += v;
    return ;
}
inline void markdown(int k,int l,int r,int mid){
    if(!add[k])return ;
    Add(k<<1,l,mid,add[k]),Add(k<<1|1,mid+1,r,add[k]);
    add[k] = 0;
    return ;
}
inline void modify(int k,int l,int r,int x,int y,int v){
    if(l>y||r<x)return ;
    if(l>=x&&r<=y){Add(k,l,r,v);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();
    for(int i=1,a,b;i<n;++i)a = re(),b = re(),add_edge(a,b),add_edge(b,a);
    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 回复 举报

看看模是不是都取了(我有一次就是没取全WA)

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。