洛谷3384
1 #include2 #include 3 #define ls (cur<<1) 4 #define rs (cur<<1|1) 5 #define len(x) (a[x].r-a[x].l+1) 6 #define mid ((a[cur].l+a[cur].r)>>1) 7 using namespace std; 8 const int maxn=500010; 9 int n,m,Mod,k,x,y,z,root,tot=0,num=0; 10 int v[maxn],pos[maxn],dfn[maxn],dep[maxn],son[maxn],size[maxn],fa[maxn],top[maxn],last[maxn]; 11 struct edge{ int to,pre;}e[maxn]; 12 struct tree{ int l,r,sum,del;}a[maxn<<2]; 13 inline void read(int &k){ 14 k=0; int f=1; char c=getchar(); 15 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 16 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 17 k*=f; 18 } 19 inline void MOD(int &k){ if (k>=Mod) k-=Mod;} 20 inline void add(int x,int y){e[++tot].to=y; e[tot].pre=last[x]; last[x]=tot;} 21 void dfs1(int x){ 22 size[x]=1; dep[x]=dep[fa[x]]+1; 23 for (int i=last[x],to;i;i=e[i].pre) 24 if ((to=e[i].to)!=fa[x]){ 25 fa[to]=x; dfs1(to); 26 size[x]+=size[to]; 27 if (size[to]>size[son[x]]) son[x]=to; 28 } 29 } 30 void dfs2(int x,int tp){ 31 top[x]=tp; dfn[x]=++num; pos[num]=x; 32 if (son[x]) dfs2(son[x],tp); 33 for (int i=last[x],to;i;i=e[i].pre) 34 if ((to=e[i].to)!=fa[x]&&to!=son[x]) dfs2(to,to); 35 } 36 void build(int cur,int l,int r){ 37 a[cur].l=l; a[cur].r=r; 38 if (l mid) add(rs,l,r,delta); 58 a[cur].sum=a[ls].sum+a[rs].sum; MOD(a[cur].sum); 59 } 60 int query(int cur,int l,int r){ 61 if (l<=a[cur].l&&a[cur].r<=r) return a[cur].sum; 62 pushdown(cur); int ret=0; 63 if (l<=mid) ret+=query(ls,l,r),MOD(ret); 64 if (r>mid) ret+=query(rs,l,r),MOD(ret); 65 return ret; 66 } 67 int main(){ 68 read(n); read(m); read(root); read(Mod); 69 for (int i=1;i<=n;i++) read(v[i]),v[i]%=Mod; 70 for (int i=1;i dep[y]) swap(x,y); 81 add(1,dfn[x],dfn[y],z); 82 } 83 if (k==2){ 84 read(x); read(y); int ans=0; 85 while(top[x]!=top[y]){ 86 if (dep[top[x]] dep[y]) swap(x,y); ans+=query(1,dfn[x],dfn[y]); MOD(ans); 90 printf("%d\n",ans); 91 } 92 if (k==3){ 93 read(x); read(y); 94 add(1,dfn[x],dfn[x]+size[x]-1,y); 95 } 96 if (k==4){ 97 read(x); 98 printf("%d\n",query(1,dfn[x],dfn[x]+size[x]-1)); 99 }100 }101 return 0;102 }