萌新妹子刚学OI,树剖20分求助

回复帖子

@Mivik 2019-09-23 10:35 回复

RT,只有1、3点AC,其他全部RE

// Mivik 2019.9.23
#include <iostream>
#include <cstdio>

#define endl '\n'
#define IO(n) freopen(#n".in","r",stdin),freopen(#n".out","w",stdout)
#define USING_R(fn,n) n fn() {static n _R;static char _C;static bool _F;_F=0;_R=0;_C=GG();while((_C<'0'||_C>'9')&&_C!='-'&&_C!='\0')_C=GG();if(_C=='-')_F=1,_C=GG();while(_C>='0'&&_C<='9')_R=(_R<<3)+(_R<<1)+_C-'0',_C=GG();if (_F) _R=-_R;return _R;}
#define USING_F(bufsize) char FGC(){static char Buffer[bufsize],*st=NULL,*en=NULL;if(st==en){en=(st=Buffer)+fread(Buffer,1,bufsize,stdin);if(st==en) return EOF;}return *st++;};
#define USING_T(a) const char* __DATA=a;char TGC(){return *__DATA++;}
#define P(a) cout<<#a"="<<(a)<<endl
#define R Read()
#define GG getchar

#define nmax 200005
#define mmax 400005
#define tmax 400005
#define lson(x) ((x)<<1)
#define rson(x) (lson(x)|1)
#define link(a,b) (pre[++tot]=lst[a],lst[a]=tot,tar[tot]=b)
#define sn(a,b) a^=b^=a^=b
using namespace std;

USING_R(Read,int)
int n,m,MOD,root;
int val[nmax];
int lst[nmax];
int pre[mmax],tar[mmax];
int siz[nmax],son[nmax];
int fa[nmax],dep[nmax];
int top[nmax],ind[nmax];
int sum[tmax],laz[tmax];
int a[nmax];
int tot;
inline void pu(int x) {sum[x]=(sum[lson(x)]+sum[rson(x)])%MOD;}
inline void pd(int x, int l1, int l2) {
    if (!laz[x]) return;
    int &l=laz[x];
    sum[lson(x)]=(sum[lson(x)]+l*l1%MOD)%MOD;
    sum[rson(x)]=(sum[rson(x)]+l*l2%MOD)%MOD;
    laz[lson(x)]+=l;
    laz[rson(x)]+=l;
    l=0;
}
void load1(int x, int f) {
    fa[x]=f;
    dep[x]=dep[fa[x]=f]+1;
    son[x]=0;
    siz[x]=1;
    for (int b=lst[x],v;b;b=pre[b]) {
        if ((v=tar[b])==f) continue;
        load1(v,x);
        if (siz[v]>siz[son[x]]) son[x]=v;
        siz[x]+=siz[v];
    }
}
void load2(int x, int tt) {
    top[x]=tt;
    ind[x]=++tot;
    a[tot]=val[x];
    if (!son[x]) return;
    load2(son[x],tt);
    for (int b=lst[x],v;b;b=pre[b]) {
        v=tar[b];
        if (v!=son[x]&&v!=fa[x]) load2(v,v);
    }
}
void build(int x, int l, int r) {
    if (l==r) {
        sum[x]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson(x),l,mid);
    build(rson(x),mid+1,r);
    pu(x);
}
int ll,rr,vv;
void update(int x, int l, int r) {
    if (ll<=l&&r<=rr) {
        sum[x]=(((r-l+1)*vv)%MOD+sum[x])%MOD;
        laz[x]+=vv;
        return;
    }
    int mid=(l+r)>>1;
    pd(x,mid-l+1,r-mid);
    if (ll<=mid) update(lson(x),l,mid);
    if (rr>mid) update(rson(x),mid+1,r);
    pu(x);
}
void updatePath(int x, int y) {
    while (top[x]!=top[y]) {
        if (dep[x]<dep[y]) sn(x,y);
        ll=ind[top[x]],rr=ind[x];
        update(1,1,n);
        x=fa[top[x]];
    }
    if (dep[x]<dep[y]) sn(x,y);
    ll=ind[y],rr=ind[x];
    update(1,1,n);
}
int query(int x, int l, int r) {
    if (ll<=l&&r<=rr) return sum[x];
    int ret=0;
    int mid=(l+r)>>1;
    pd(x,mid-l+1,r-mid);
    if (ll<=mid) ret=(ret+query(lson(x),l,mid))%MOD;
    if (rr>mid) ret=(ret+query(rson(x),mid+1,r))%MOD;
    return ret;
}
int queryPath(int x, int y) {
    int ret=0;
    while (top[x]!=top[y]) {
        if (dep[x]<dep[y]) sn(x,y);
        ll=ind[top[x]],rr=ind[x];
        ret=(ret+query(1,1,n))%MOD;
        x=fa[top[x]];
    }
    if (dep[x]<dep[y]) sn(x,y);
    ll=ind[y],rr=ind[x];
    return (ret+query(1,1,n))%MOD;
}
int main() {
    n=R,m=R,root=R,MOD=R;
    register int i,x,y;
    for (i=1;i<=n;i++) val[i]=R%MOD;
    tot=0;
    for (i=1;i<n;i++) {
        x=R,y=R;
        link(x,y);
        link(y,x);
    }
    load1(root,0);
    tot=0;
    load2(root,root);
    build(1,1,n);
    while (m--) {
        i=R,x=R;
        switch (i) {
            case 1:y=R;vv=R%MOD;updatePath(x,y);break;
            case 2:y=R;cout<<queryPath(x,y)<<endl;break;
            case 3:vv=R%MOD;ll=ind[x];rr=ind[x]+siz[x]-1;update(1,1,n);break;
            case 4:ll=ind[x];rr=ind[x]+siz[x]-1;cout<<query(1,1,n)<<endl;break;
        }
    }
    return 0;
}
@deco  2019-09-23 10:38 回复 举报

mivik真的是妹子,不管不是萌新,我知道的

@Mivik 2019-09-23 10:49 回复 举报

问题解决:
dep[x]<dep[y]应该改成dep[top[x]]<dep[top[y]]
QwQ

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



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