# 萌新妹子刚学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 GG getchar

#define nmax 200005
#define mmax 400005
#define tmax 400005
#define lson(x) ((x)<<1)
#define rson(x) (lson(x)|1)
#define sn(a,b) a^=b^=a^=b
using namespace std;

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;
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;
for (int b=lst[x],v;b;b=pre[b]) {
v=tar[b];
}
}
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;
}
tot=0;
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真的是妹子，不管不是萌新，我知道的

@Eason_AC 2019-09-23 10:45 回复 举报

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

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

dep[x]<dep[y]应该改成dep[top[x]]<dep[top[y]]
QwQ