2020-2021:teams:legal_string:树链剖分_lgwza
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:树链剖分_lgwza [2020/08/04 22:20] lgwza |
2020-2021:teams:legal_string:树链剖分_lgwza [2020/08/04 22:21] (当前版本) lgwza [例题] |
||
|---|---|---|---|
| 行 182: | 行 182: | ||
| ===== 例题 ===== | ===== 例题 ===== | ||
| [[https://www.luogu.com.cn/problem/P3384|P3384 【模板】轻重链剖分]] | [[https://www.luogu.com.cn/problem/P3384|P3384 【模板】轻重链剖分]] | ||
| + | |||
| + | 参考代码： | ||
| + | |||
| + | <hidden> | ||
| + | <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | const int N=1e5+5; | ||
| + | typedef long long ll; | ||
| + | |||
| + | int n,m,root,mod; | ||
| + | int cnt,head[N],nxt[N<<1],to[N<<1],w[N],nw[N]; | ||
| + | int tr[N<<2],add[N<<2]; | ||
| + | int hson[N],dfn[N],fa[N],tot,dep[N],siz[N],top[N],rk[N]; | ||
| + | void addedge(int u,int v){ | ||
| + | nxt[++cnt]=head[u]; | ||
| + | head[u]=cnt; | ||
| + | to[cnt]=v; | ||
| + | } | ||
| + | // segment tree | ||
| + | inline int ls(int o){ | ||
| + | return o<<1; | ||
| + | } | ||
| + | inline int rs(int o){ | ||
| + | return o<<1|1; | ||
| + | } | ||
| + | void push_up(int o){ | ||
| + | tr[o]=(tr[ls(o)]+tr[rs(o)])%mod; | ||
| + | } | ||
| + | void build(int o,int l,int r){ | ||
| + | if(l==r){ | ||
| + | tr[o]=nw[l]%mod; | ||
| + | return; | ||
| + | } | ||
| + | int mid=l+r>>1; | ||
| + | build(ls(o),l,mid); | ||
| + | build(rs(o),mid+1,r); | ||
| + | push_up(o); | ||
| + | } | ||
| + | void f(int o,int l,int r,int k){ | ||
| + | add[o]=(add[o]+k); | ||
| + | tr[o]=(tr[o]+(r-l+1)*k)%mod; | ||
| + | } | ||
| + | void push_down(int o,int l,int r){ | ||
| + | int mid=l+r>>1; | ||
| + | f(ls(o),l,mid,add[o]); | ||
| + | f(rs(o),mid+1,r,add[o]); | ||
| + | add[o]=0; | ||
| + | } | ||
| + | void xg(int o,int nl,int nr,int l,int r,int k){ | ||
| + | if(nl<=l&&r<=nr){ | ||
| + | add[o]=(add[o]+k)%mod; | ||
| + | tr[o]=(tr[o]+(r-l+1)*k)%mod; | ||
| + | return; | ||
| + | } | ||
| + | push_down(o,l,r); | ||
| + | int mid=l+r>>1; | ||
| + | if(nl<=mid) xg(ls(o),nl,nr,l,mid,k); | ||
| + | if(nr>mid) xg(rs(o),nl,nr,mid+1,r,k); | ||
| + | push_up(o); | ||
| + | } | ||
| + | int cx(int o,int nl,int nr,int l,int r){ | ||
| + | if(nl<=l&&r<=nr) return tr[o]%mod; | ||
| + | push_down(o,l,r); | ||
| + | int ret=0; | ||
| + | int mid=l+r>>1; | ||
| + | if(nl<=mid) ret+=cx(ls(o),nl,nr,l,mid); | ||
| + | if(nr>mid) ret+=cx(rs(o),nl,nr,mid+1,r); | ||
| + | return ret%mod; | ||
| + | } | ||
| + | // original tree | ||
| + | int cxRange(int x,int y){ | ||
| + | int ans=0; | ||
| + | while(top[x]!=top[y]){ | ||
| + | if(dep[top[x]]<dep[top[y]]) swap(x,y); | ||
| + | ans+=cx(1,dfn[top[x]],dfn[x],1,n); | ||
| + | ans%=mod; | ||
| + | x=fa[top[x]]; | ||
| + | } | ||
| + | if(dep[x]>dep[y]) swap(x,y); | ||
| + | ans+=cx(1,dfn[x],dfn[y],1,n); | ||
| + | ans%=mod; | ||
| + | return ans; | ||
| + | } | ||
| + | void xgRange(int x,int y,int k){ | ||
| + | k%=mod; | ||
| + | while(top[x]!=top[y]){ | ||
| + | if(dep[top[x]]<dep[top[y]]) swap(x,y); | ||
| + | xg(1,dfn[top[x]],dfn[x],1,n,k); | ||
| + | x=fa[top[x]]; | ||
| + | } | ||
| + | if(dep[x]>dep[y]) swap(x,y); | ||
| + | xg(1,dfn[x],dfn[y],1,n,k); | ||
| + | } | ||
| + | int cxSon(int x){ | ||
| + | return cx(1,dfn[x],dfn[x]+siz[x]-1,1,n); | ||
| + | } | ||
| + | void xgSon(int x,int k){ | ||
| + | xg(1,dfn[x],dfn[x]+siz[x]-1,1,n,k); | ||
| + | } | ||
| + | // dfs | ||
| + | void dfs1(int u,int f,int deep){ | ||
| + | dep[u]=deep; | ||
| + | siz[u]=1; | ||
| + | fa[u]=f; | ||
| + | for(int i=head[u];i;i=nxt[i]){ | ||
| + | int v=to[i]; | ||
| + | if(v==fa[u]) continue; | ||
| + | dfs1(v,u,deep+1); | ||
| + | siz[u]+=siz[v]; | ||
| + | if(hson[u]==0||siz[hson[u]]<siz[v]) hson[u]=v; | ||
| + | } | ||
| + | } | ||
| + | void dfs2(int u,int t){ | ||
| + | top[u]=t; | ||
| + | dfn[u]=++tot; | ||
| + | nw[tot]=w[u]; | ||
| + | rk[tot]=u; | ||
| + | if(!hson[u]) return; | ||
| + | dfs2(hson[u],t); | ||
| + | for(int i=head[u];i;i=nxt[i]){ | ||
| + | int v=to[i]; | ||
| + | if(v==fa[u]||v==hson[u]) continue; | ||
| + | dfs2(v,v); | ||
| + | } | ||
| + | } | ||
| + | int main(){ | ||
| + | scanf("%d %d %d %d",&n,&m,&root,&mod); | ||
| + | for(int i=1;i<=n;i++) scanf("%d",&w[i]); | ||
| + | for(int i=1;i<=n-1;i++){ | ||
| + | int x,y; | ||
| + | scanf("%d %d",&x,&y); | ||
| + | addedge(x,y); | ||
| + | addedge(y,x); | ||
| + | } | ||
| + | dfs1(root,0,1); | ||
| + | dfs2(root,root); | ||
| + | build(1,1,n); | ||
| + | // printf("fadfa\n"); | ||
| + | while(m--){ | ||
| + | int op; | ||
| + | scanf("%d",&op); | ||
| + | if(op==1){ | ||
| + | int x,y; | ||
| + | int k; | ||
| + | scanf("%d %d %d",&x,&y,&k); | ||
| + | k%=mod; | ||
| + | xgRange(x,y,k); | ||
| + | } | ||
| + | else if(op==2){ | ||
| + | int x,y; | ||
| + | scanf("%d %d",&x,&y); | ||
| + | printf("%d\n",cxRange(x,y)); | ||
| + | } | ||
| + | else if(op==3){ | ||
| + | int x; | ||
| + | int k; | ||
| + | scanf("%d %d",&x,&k); | ||
| + | k%=mod; | ||
| + | xgSon(x,k); | ||
| + | } | ||
| + | else if(op==4){ | ||
| + | int x; | ||
| + | scanf("%d",&x); | ||
| + | printf("%d\n",cxSon(x)); | ||
| + | } | ||
| + | } | ||
| + | |||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| ===== 参考资料 ===== | ===== 参考资料 ===== | ||
| [[https://oi-wiki.org/graph/hld/|OI Wiki]] | [[https://oi-wiki.org/graph/hld/|OI Wiki]] | ||
2020-2021/teams/legal_string/树链剖分_lgwza.1596550823.txt.gz · 最后更改: 2020/08/04 22:20 由 lgwza
