2020-2021:teams:legal_string:jxm2001:重链剖分
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:重链剖分 [2020/07/26 12:08] jxm2001 |
2020-2021:teams:legal_string:jxm2001:重链剖分 [2021/08/04 20:37] (当前版本) jxm2001 [代码模板] |
||
|---|---|---|---|
| 行 115: | 行 115: | ||
| head[u]=m; | head[u]=m; | ||
| } | } | ||
| - | int d[MAXN],w[MAXN],sz[MAXN],f[MAXN],dfs_id[MAXN],dfs_t; | + | int d[MAXN],w[MAXN],sz[MAXN],f[MAXN],dfn[MAXN],dfs_t; |
| - | int h_son[MAXN],mson[MAXN],p[MAXN],dfs_w[MAXN]; | + | int h_son[MAXN],mson[MAXN],p[MAXN],dfw[MAXN]; |
| void dfs_1(int u,int fa,int depth){ | void dfs_1(int u,int fa,int depth){ | ||
| - | sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0; | + | sz[u]=1,f[u]=fa,d[u]=depth,mson[u]=0; |
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| int v=edge[i].to; | int v=edge[i].to; | ||
| 行 132: | 行 132: | ||
| } | } | ||
| void dfs_2(int u,int top){ | void dfs_2(int u,int top){ | ||
| - | dfs_id[u]=++dfs_t;p[u]=top;dfs_w[dfs_t]=w[u]; | + | dfn[u]=++dfs_t,p[u]=top; |
| + | dfw[dfs_t]=w[u]; | ||
| if(mson[u]) | if(mson[u]) | ||
| dfs_2(h_son[u],top); | dfs_2(h_son[u],top); | ||
| 行 142: | 行 143: | ||
| } | } | ||
| } | } | ||
| - | LL query_son(int u){return tree.query(1,dfs_id[u],dfs_id[u]+sz[u]-1);} | + | int query_path(int u,int v){ |
| - | void update_son(int u,int w){tree.update(1,dfs_id[u],dfs_id[u]+sz[u]-1,w);} | + | |
| - | LL query_path(int u,int v){ | + | |
| LL ans=0; | LL ans=0; | ||
| while(p[u]!=p[v]){ | while(p[u]!=p[v]){ | ||
| if(d[p[u]]<d[p[v]]) | if(d[p[u]]<d[p[v]]) | ||
| swap(u,v); | swap(u,v); | ||
| - | ans=(ans+tree.query(1,dfs_id[p[u]],dfs_id[u]))%mod; | + | ans=(ans+tree.query(1,dfn[p[u]],dfn[u]))%mod; |
| u=f[p[u]]; | u=f[p[u]]; | ||
| } | } | ||
| if(d[u]>d[v]) | if(d[u]>d[v]) | ||
| swap(u,v); | swap(u,v); | ||
| - | ans=(ans+tree.query(1,dfs_id[u],dfs_id[v]))%mod; | + | ans=(ans+tree.query(1,dfn[u],dfn[v]))%mod; |
| return ans; | return ans; | ||
| } | } | ||
| 行 161: | 行 160: | ||
| if(d[p[u]]<d[p[v]]) | if(d[p[u]]<d[p[v]]) | ||
| swap(u,v); | swap(u,v); | ||
| - | tree.update(1,dfs_id[p[u]],dfs_id[u],w); | + | tree.update(1,dfn[p[u]],dfn[u],w); |
| u=f[p[u]]; | u=f[p[u]]; | ||
| } | } | ||
| if(d[u]>d[v]) | if(d[u]>d[v]) | ||
| swap(u,v); | swap(u,v); | ||
| - | tree.update(1,dfs_id[u],dfs_id[v],w); | + | tree.update(1,dfn[u],dfn[v],w); |
| } | } | ||
| + | int query_son(int u){return tree.query(1,dfn[u],dfn[u]+sz[u]-1);} | ||
| + | void update_son(int u,int w){tree.update(1,dfn[u],dfn[u]+sz[u]-1,w);} | ||
| int main() | int main() | ||
| { | { | ||
2020-2021/teams/legal_string/jxm2001/重链剖分.1595736504.txt.gz · 最后更改: 2020/07/26 12:08 由 jxm2001
