# 树链剖分 树链剖分将树分割成若干条链的形式，可以维护子树或者链的信息。主要用到重链剖分。 ## 重链剖分 ### 预处理 我们给出一些定义： **重儿子**：任意一个子树大小最大的儿子 **轻儿子**：剩下的儿子 **重边**：到重儿子的边 **轻边**：到轻儿子的边 **重链**：首尾相接的若干条重边 下图来自[OI-wiki](https://oi-wiki.org/graph/hld/)：  我们要求出以上东西，需要维护以下信息： $fa[x]$ 表示 $x$ 的父亲 $dep[x]$ 表示 $x$ 的深度 $siz[x]$ 表示 $x$ 子树大小 $top[x]$ 表示 $x$ 所在重链的顶点 $dfn[x]$ 表示 $x$ 的dfs序 $rnk[x]$ 表示dfs序对应的节点编号 我们可以用2个dfs求出： ```c++ void dfs1(int x) { dep[x]=dep[fa[x]]+1; siz[x]=1; for (int i=0; i<e[x].size(); i++) { int y=e[x][i]; if (y==fa[x]) continue; fa[y]=x; dfs1(y); siz[x]+=siz[y]; if (siz[y]>siz[son[x]]) son[x]=y; } } void dfs2(int x, int t) { top[x]=t; dfn[x]=++cnt; rnk[cnt]=x; if (!son[x]) return; dfs2(son[x], t); for (int i=0; i<e[x].size(); i++) if(e[x][i]!=fa[x] && e[x][i]!=son[x]) dfs2(e[x][i], e[x][i]); } ``` ### LCA 有了这些，我们可以在 $O(\log n)$ 的时间内求出 $2$ 个点的 lca 。 简单来说，就是 $2$ 个点重链顶端深度最小的节点跳到重链顶端，最后深度较小的结点就是 lca 。 代码实现： ```c++ int lca(int x, int y) { while (top[x]!=top[y]) if (dep[top[x]]>dep[top[y]]) x=fa[top[x]]; else y=fa[top[y]]; return dep[x]<dep[y] ? x : y; } ``` ### 子树修改、查询 我们发现，dfs 序是连续的，所以子树就对应 dfs 序上的一个区间，于是，子树操作就变成了区间操作，我们可以用一些数据结构来维护。 线段树维护区间和： ```c++ #define lp p<<1 #define rp p<<1|1 void build(int p, int L, int R) { l[p]=L, r[p]=R; if (L==R) { s[p]=a[rnk[L]]; return; } int mid=L+R>>1; build(lp, L, mid); build(rp, mid+1, R); s[p]=(s[lp]+s[rp])%mod; } void pushdown(int p) { s[lp]=(s[lp]+(r[lp]-l[lp]+1)*t[p])%mod; s[rp]=(s[rp]+(r[rp]-l[rp]+1)*t[p])%mod; t[lp]=(t[lp]+t[p])%mod, t[rp]=(t[rp]+t[p])%mod, t[p]=0; } void change(int p, int L, int R, int v) { if (L<=l[p] && r[p]<=R) { t[p]=(t[p]+v)%mod; s[p]=(s[p]+(r[p]-l[p]+1)*v)%mod; return; } pushdown(p); int mid=l[p]+r[p]>>1; if (L<=mid) change(lp, L, R, v); if (R>mid) change(rp, L, R, v); s[p]=(s[lp]+s[rp])%mod; } int query(int p, int L, int R) { if (L<=l[p] && r[p]<=R) return s[p]; pushdown(p); int mid=l[p]+r[p]>>1, r=0; if (L<=mid) r+=query(lp, L, R); if (R>mid) r+=query(rp, L, R); return r; } ``` 子树修改、查询： ```c++ void change_tree(int x, int v) { change(1, dfn[x], dfn[x]+siz[x]-1, v); } int query_tree(int x) { return query(1, dfn[x], dfn[x]+siz[x]-1); } ``` ### 链修改、查询 我们发现这和求 lca 相似，在向上跳的过程中，如果当前节点在重链上，向上跳到重链顶端，如果当前节点不在重链上，向上跳一个节点。如此直到两节点相同。沿途更新/查询区间信息。 对于每个询问，最多经过 $O(\log n)$ 条重链，每条重链上线段树的复杂度为 $O(\log n)$ ，所以修改一次的复杂度是 $O(\log^2 n)$ 。 具体代码： ```c++ void change_chain(int x, int y, int z) { int fx=top[x], fy=top[y]; while (fx!=fy) { if (dep[fx]>=dep[fy]) change(1, dfn[fx], dfn[x], z), x=fa[fx]; else change(1, dfn[fy], dfn[y], z), y=fa[fy]; fx=top[x], fy=top[y]; } change(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), z); } int query_chain(int x, int y) { int res=0, fx=top[x], fy=top[y]; while (fx!=fy) { if (dep[fx]>=dep[fy]) res=(res+query(1, dfn[fx], dfn[x])%mod), x=fa[fx]; else res=(res+query(1, dfn[fy], dfn[y]))%mod, y=fa[fy]; fx=top[x], fy=top[y]; } res=(res+query(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y])))%mod; return res; } ``` ## 例题 ### [Luogu P3384 【模板】轻重链剖分/树链剖分](https://www.luogu.com.cn/problem/P3384) 把上面的操作结合起来，不需要求 lca ，注意运算时取模就可以了。 时间复杂度：$O(n\log n+q\log^2n)$ 代码： ```c++ #include <cstdio> #include <cctype> #include <vector> #include <algorithm> #define int long long using namespace std; const int N=4e5+10; int fa[N], dep[N], siz[N], son[N], top[N], dfn[N], rnk[N]; int n, m, rt, mod, a[N], cnt; int l[N], r[N], s[N], t[N]; vector<int> e[N]; int read() { int x=0, f=0; char ch=getchar(); while (!isdigit(ch)) {f|=ch=='-'; ch=getchar();} while (isdigit(ch)) {x=(x<<3)+(x<<1)+(ch^48); ch=getchar();} return f?-x:x; } void dfs1(int x) { dep[x]=dep[fa[x]]+1; siz[x]=1; for (int i=0; i<e[x].size(); i++) { int y=e[x][i]; if (y==fa[x]) continue; fa[y]=x; dfs1(y); siz[x]+=siz[y]; if (siz[y]>siz[son[x]]) son[x]=y; } } void dfs2(int x, int t) { top[x]=t; dfn[x]=++cnt; rnk[cnt]=x; if (!son[x]) return; dfs2(son[x], t); for (int i=0; i<e[x].size(); i++) if(e[x][i]!=fa[x] && e[x][i]!=son[x]) dfs2(e[x][i], e[x][i]); } int lca(int x, int y) { while (top[x]!=top[y]) if (dep[top[x]]>dep[top[y]]) x=fa[top[x]]; else y=fa[top[y]]; return dep[x]<dep[y] ? x : y; } #define lp p<<1 #define rp p<<1|1 void build(int p, int L, int R) { l[p]=L, r[p]=R; if (L==R) { s[p]=a[rnk[L]]; return; } int mid=L+R>>1; build(lp, L, mid); build(rp, mid+1, R); s[p]=(s[lp]+s[rp])%mod; } void pushdown(int p) { s[lp]=(s[lp]+(r[lp]-l[lp]+1)*t[p])%mod; s[rp]=(s[rp]+(r[rp]-l[rp]+1)*t[p])%mod; t[lp]=(t[lp]+t[p])%mod, t[rp]=(t[rp]+t[p])%mod, t[p]=0; } void change(int p, int L, int R, int v) { if (L<=l[p] && r[p]<=R) { t[p]=(t[p]+v)%mod; s[p]=(s[p]+(r[p]-l[p]+1)*v)%mod; return; } pushdown(p); int mid=l[p]+r[p]>>1; if (L<=mid) change(lp, L, R, v); if (R>mid) change(rp, L, R, v); s[p]=(s[lp]+s[rp])%mod; } int query(int p, int L, int R) { if (L<=l[p] && r[p]<=R) return s[p]; pushdown(p); int mid=l[p]+r[p]>>1, r=0; if (L<=mid) r=(r+query(lp, L, R))%mod; if (R>mid) r=(r+query(rp, L, R))%mod; return r; } void change_tree(int x, int v) { change(1, dfn[x], dfn[x]+siz[x]-1, v); } int query_tree(int x) { return query(1, dfn[x], dfn[x]+siz[x]-1); } void change_chain(int x, int y, int z) { int fx=top[x], fy=top[y]; while (fx!=fy) { if (dep[fx]>=dep[fy]) change(1, dfn[fx], dfn[x], z), x=fa[fx]; else change(1, dfn[fy], dfn[y], z), y=fa[fy]; fx=top[x], fy=top[y]; } change(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), z); } int query_chain(int x, int y) { int res=0, fx=top[x], fy=top[y]; while (fx!=fy) { if (dep[fx]>=dep[fy]) res=(res+query(1, dfn[fx], dfn[x]))%mod, x=fa[fx]; else res=(res+query(1, dfn[fy], dfn[y]))%mod, y=fa[fy]; fx=top[x], fy=top[y]; } res=(res+query(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y])))%mod; return res; } signed main() { n=read(), m=read(), rt=read(), mod=read(); for (int i=1; i<=n; i++) a[i]=read(); for (int i=1; i<n; i++) { int x=read(), y=read(); e[x].push_back(y); e[y].push_back(x); } dfs1(rt); dfs2(rt, rt); build(1, 1, n); while (m--) { int opt=read(); if (opt==1) { int x=read(), y=read(), z=read();; change_chain(x, y, z); } else if (opt==2) { int x=read(), y=read(); printf("%lld\n", query_chain(x, y)); } else if (opt==3) { int x=read(), z=read(); change_tree(x, z); } else { int x=read(); printf("%lld\n", query_tree(x)); } } return 0; } ``` --- ### [Luogu P1505 [国家集训队]旅游](https://www.luogu.com.cn/problem/P1505) 题意自己看吧 显然也是一道板子题，操作变多了一些， 最大值最小值线段树都可以维护。 因为题目里操作的是边，我们可以把边权记录到点上，把每个点的点权设为他到父亲的边权，这样每次修改或查询的时候不能算它们 lca 的权值，其它的都要算上，这样在做完链操作后靠上面的节点是 lca ，从它后一位开始做即可。 修改后代码如下 ```c++ if (dfn[x]>dfn[y]) res=min(res, ask_min(1, dfn[y]+1, dfn[x])); else if (dfn[y]>dfn[x]) res=min(res, ask_min(1, dfn[x]+1, dfn[y])); ``` 完整代码： ```c++ #include <cstdio> #include <cctype> #include <utility> #include <vector> #define lp p<<1 #define rp p<<1|1 using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=1e6+10; int n, m, v[N], X[N], Y[N], sz[N], fa[N], son[N], top[N], dfn[N], dep[N], dfncnt; int l[N], r[N], s[N], mn[N], mx[N], t[N]; vector<pair<int, int> >e[N]; void dfs1(int x) { sz[x]=1; dep[x]=dep[fa[x]]+1; for (int i=0; i<e[x].size(); i++) { int y=e[x][i].first; if (y==fa[x]) continue; fa[y]=x; dfs1(y); sz[x]+=sz[y]; if (sz[y]>sz[son[x]]) son[x]=y; } } void dfs2(int x, int t) { top[x]=t; dfn[x]=++dfncnt; if (!son[x]) return; dfs2(son[x], t); for (int i=0; i<e[x].size(); i++) { int y=e[x][i].first; if (y==fa[x] || y==son[x]) continue; dfs2(y, y); } } void build(int p, int L, int R) { l[p]=L, r[p]=R; if (L==R) return s[p]=mx[p]=mn[p]=v[L], void(); int mid=L+R>>1; build(lp, L, mid); build(rp, mid+1, R); s[p]=s[lp]+s[rp]; mx[p]=max(mx[lp], mx[rp]); mn[p]=min(mn[lp], mn[rp]); } void pushdown(int p) { if (!t[p]) return; t[lp]^=1; s[lp]=-s[lp]; swap(mx[lp], mn[lp]); mx[lp]=-mx[lp]; mn[lp]=-mn[lp]; t[rp]^=1; s[rp]=-s[rp]; swap(mx[rp], mn[rp]); mx[rp]=-mx[rp]; mn[rp]=-mn[rp]; t[p]=0; } void qufan(int p, int L, int R) { pushdown(p); if (L<=l[p] && r[p]<=R) { s[p]=-s[p]; swap(mx[p], mn[p]); mx[p]=-mx[p]; mn[p]=-mn[p]; t[p]=1; return; } int mid=l[p]+r[p]>>1; if (L<=mid) qufan(lp, L, R); if (R>mid) qufan(rp, L, R); s[p]=s[lp]+s[rp]; mx[p]=max(mx[lp], mx[rp]); mn[p]=min(mn[lp], mn[rp]); } void change(int p, int x, int k) { pushdown(p); if (l[p]==r[p]) return s[p]=mx[p]=mn[p]=k, void(); int mid=l[p]+r[p]>>1; if (x<=mid) change(lp, x, k); else change(rp, x, k); s[p]=s[lp]+s[rp]; mx[p]=max(mx[lp], mx[rp]); mn[p]=min(mn[lp], mn[rp]); } int ask_sum(int p, int L, int R) { pushdown(p); if (L<=l[p] && r[p]<=R) return s[p]; int mid=l[p]+r[p]>>1, sum=0; if (L<=mid) sum+=ask_sum(lp, L, R); if (R>mid) sum+=ask_sum(rp, L, R); return sum; } int ask_min(int p, int L, int R) { pushdown(p); if (L<=l[p] && r[p]<=R) return mn[p]; int mid=l[p]+r[p]>>1, res=2e9; if (L<=mid) res=min(res, ask_min(lp, L, R)); if (R>mid) res=min(res, ask_min(rp, L, R)); return res; } int ask_max(int p, int L, int R) { pushdown(p); if (L<=l[p] && r[p]<=R) return mx[p]; int mid=l[p]+r[p]>>1, res=-2e9; if (L<=mid) res=max(res, ask_max(lp, L, R)); if (R>mid) res=max(res, ask_max(rp, L, R)); return res; } void qufan_chain(int x, int y) { int fx=top[x], fy=top[y]; while (fx!=fy) { if (dep[fx]>=dep[fy]) qufan(1, dfn[fx], dfn[x]), x=fa[fx]; else qufan(1, dfn[fy], dfn[y]), y=fa[fy]; fx=top[x], fy=top[y]; } if (dfn[x]>dfn[y]) qufan(1, dfn[y]+1, dfn[x]); else if (dfn[y]>dfn[x]) qufan(1, dfn[x]+1, dfn[y]); } int sum_chain(int x, int y) { int fx=top[x], fy=top[y], res=0; while (fx!=fy) { if (dep[fx]>=dep[fy]) res+=ask_sum(1, dfn[fx], dfn[x]), x=fa[fx]; else res+=ask_sum(1, dfn[fy], dfn[y]), y=fa[fy]; fx=top[x], fy=top[y]; } if (dfn[x]>dfn[y]) res+=ask_sum(1, dfn[y]+1, dfn[x]); else if (dfn[y]>dfn[x]) res+=ask_sum(1, dfn[x]+1, dfn[y]); return res; } int max_chain(int x, int y) { int fx=top[x], fy=top[y], res=-2e9; while (fx!=fy) { if (dep[fx]>=dep[fy]) res=max(res, ask_max(1, dfn[fx], dfn[x])), x=fa[fx]; else res=max(res, ask_max(1, dfn[fy], dfn[y])), y=fa[fy]; fx=top[x], fy=top[y]; } if (dfn[x]>dfn[y]) res=max(res, ask_max(1, dfn[y]+1, dfn[x])); else if (dfn[y]>dfn[x]) res=max(res, ask_max(1, dfn[x]+1, dfn[y])); return res; } int min_chain(int x, int y) { int fx=top[x], fy=top[y], res=2e9; while (fx!=fy) { if (dep[fx]>=dep[fy]) res=min(res, ask_min(1, dfn[fx], dfn[x])), x=fa[fx]; else res=min(res, ask_min(1, dfn[fy], dfn[y])), y=fa[fy]; fx=top[x], fy=top[y]; } if (dfn[x]>dfn[y]) res=min(res, ask_min(1, dfn[y]+1, dfn[x])); else if (dfn[y]>dfn[x]) res=min(res, ask_min(1, dfn[x]+1, dfn[y])); return res; } int main() { int n=read(); for (int i=1; i<n; i++) { int x=read()+1, y=read()+1, z=read(); e[x].push_back(make_pair(y, z)); e[y].push_back(make_pair(x, z)); X[i]=x; Y[i]=y; } dfs1(1); dfs2(1, 1); for (int x=1; x<=n; x++) { for (int i=0; i<e[x].size(); i++) { int y=e[x][i].first; if (fa[x]==y) v[dfn[x]]=e[x][i].second; } } build(1, 1, n); int m=read(); while (m--) { char s[10]; scanf("%s", s+1); int x=read(), y=read(); if (s[1]=='C') { int t; if (fa[X[x]]==Y[x]) t=X[x]; else t=Y[x]; change(1, dfn[t], y); } if (s[1]=='N') qufan_chain(x+1, y+1); if (s[1]=='S') printf("%d\n", sum_chain(x+1, y+1)); if (s[1]=='M' && s[2]=='A') printf("%d\n", max_chain(x+1, y+1)); if (s[1]=='M' && s[2]=='I') printf("%d\n", min_chain(x+1, y+1)); } return 0; } ``` ## 参考 1. [OI-wiki](https://oi-wiki.org/graph/hld/) Loading... # 树链剖分 树链剖分将树分割成若干条链的形式，可以维护子树或者链的信息。主要用到重链剖分。 ## 重链剖分 ### 预处理 我们给出一些定义： **重儿子**：任意一个子树大小最大的儿子 **轻儿子**：剩下的儿子 **重边**：到重儿子的边 **轻边**：到轻儿子的边 **重链**：首尾相接的若干条重边 下图来自[OI-wiki](https://oi-wiki.org/graph/hld/)：  我们要求出以上东西，需要维护以下信息： $fa[x]$ 表示 $x$ 的父亲 $dep[x]$ 表示 $x$ 的深度 $siz[x]$ 表示 $x$ 子树大小 $top[x]$ 表示 $x$ 所在重链的顶点 $dfn[x]$ 表示 $x$ 的dfs序 $rnk[x]$ 表示dfs序对应的节点编号 我们可以用2个dfs求出： ```c++ void dfs1(int x) { dep[x]=dep[fa[x]]+1; siz[x]=1; for (int i=0; i<e[x].size(); i++) { int y=e[x][i]; if (y==fa[x]) continue; fa[y]=x; dfs1(y); siz[x]+=siz[y]; if (siz[y]>siz[son[x]]) son[x]=y; } } void dfs2(int x, int t) { top[x]=t; dfn[x]=++cnt; rnk[cnt]=x; if (!son[x]) return; dfs2(son[x], t); for (int i=0; i<e[x].size(); i++) if(e[x][i]!=fa[x] && e[x][i]!=son[x]) dfs2(e[x][i], e[x][i]); } ``` ### LCA 有了这些，我们可以在 $O(\log n)$ 的时间内求出 $2$ 个点的 lca 。 简单来说，就是 $2$ 个点重链顶端深度最小的节点跳到重链顶端，最后深度较小的结点就是 lca 。 代码实现： ```c++ int lca(int x, int y) { while (top[x]!=top[y]) if (dep[top[x]]>dep[top[y]]) x=fa[top[x]]; else y=fa[top[y]]; return dep[x]<dep[y] ? x : y; } ``` ### 子树修改、查询 我们发现，dfs 序是连续的，所以子树就对应 dfs 序上的一个区间，于是，子树操作就变成了区间操作，我们可以用一些数据结构来维护。 线段树维护区间和： ```c++ #define lp p<<1 #define rp p<<1|1 void build(int p, int L, int R) { l[p]=L, r[p]=R; if (L==R) { s[p]=a[rnk[L]]; return; } int mid=L+R>>1; build(lp, L, mid); build(rp, mid+1, R); s[p]=(s[lp]+s[rp])%mod; } void pushdown(int p) { s[lp]=(s[lp]+(r[lp]-l[lp]+1)*t[p])%mod; s[rp]=(s[rp]+(r[rp]-l[rp]+1)*t[p])%mod; t[lp]=(t[lp]+t[p])%mod, t[rp]=(t[rp]+t[p])%mod, t[p]=0; } void change(int p, int L, int R, int v) { if (L<=l[p] && r[p]<=R) { t[p]=(t[p]+v)%mod; s[p]=(s[p]+(r[p]-l[p]+1)*v)%mod; return; } pushdown(p); int mid=l[p]+r[p]>>1; if (L<=mid) change(lp, L, R, v); if (R>mid) change(rp, L, R, v); s[p]=(s[lp]+s[rp])%mod; } int query(int p, int L, int R) { if (L<=l[p] && r[p]<=R) return s[p]; pushdown(p); int mid=l[p]+r[p]>>1, r=0; if (L<=mid) r+=query(lp, L, R); if (R>mid) r+=query(rp, L, R); return r; } ``` 子树修改、查询： ```c++ void change_tree(int x, int v) { change(1, dfn[x], dfn[x]+siz[x]-1, v); } int query_tree(int x) { return query(1, dfn[x], dfn[x]+siz[x]-1); } ``` ### 链修改、查询 我们发现这和求 lca 相似，在向上跳的过程中，如果当前节点在重链上，向上跳到重链顶端，如果当前节点不在重链上，向上跳一个节点。如此直到两节点相同。沿途更新/查询区间信息。 对于每个询问，最多经过 $O(\log n)$ 条重链，每条重链上线段树的复杂度为 $O(\log n)$ ，所以修改一次的复杂度是 $O(\log^2 n)$ 。 具体代码： ```c++ void change_chain(int x, int y, int z) { int fx=top[x], fy=top[y]; while (fx!=fy) { if (dep[fx]>=dep[fy]) change(1, dfn[fx], dfn[x], z), x=fa[fx]; else change(1, dfn[fy], dfn[y], z), y=fa[fy]; fx=top[x], fy=top[y]; } change(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), z); } int query_chain(int x, int y) { int res=0, fx=top[x], fy=top[y]; while (fx!=fy) { if (dep[fx]>=dep[fy]) res=(res+query(1, dfn[fx], dfn[x])%mod), x=fa[fx]; else res=(res+query(1, dfn[fy], dfn[y]))%mod, y=fa[fy]; fx=top[x], fy=top[y]; } res=(res+query(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y])))%mod; return res; } ``` ## 例题 ### [Luogu P3384 【模板】轻重链剖分/树链剖分](https://www.luogu.com.cn/problem/P3384) 把上面的操作结合起来，不需要求 lca ，注意运算时取模就可以了。 时间复杂度：$O(n\log n+q\log^2n)$ 代码： ```c++ #include <cstdio> #include <cctype> #include <vector> #include <algorithm> #define int long long using namespace std; const int N=4e5+10; int fa[N], dep[N], siz[N], son[N], top[N], dfn[N], rnk[N]; int n, m, rt, mod, a[N], cnt; int l[N], r[N], s[N], t[N]; vector<int> e[N]; int read() { int x=0, f=0; char ch=getchar(); while (!isdigit(ch)) {f|=ch=='-'; ch=getchar();} while (isdigit(ch)) {x=(x<<3)+(x<<1)+(ch^48); ch=getchar();} return f?-x:x; } void dfs1(int x) { dep[x]=dep[fa[x]]+1; siz[x]=1; for (int i=0; i<e[x].size(); i++) { int y=e[x][i]; if (y==fa[x]) continue; fa[y]=x; dfs1(y); siz[x]+=siz[y]; if (siz[y]>siz[son[x]]) son[x]=y; } } void dfs2(int x, int t) { top[x]=t; dfn[x]=++cnt; rnk[cnt]=x; if (!son[x]) return; dfs2(son[x], t); for (int i=0; i<e[x].size(); i++) if(e[x][i]!=fa[x] && e[x][i]!=son[x]) dfs2(e[x][i], e[x][i]); } int lca(int x, int y) { while (top[x]!=top[y]) if (dep[top[x]]>dep[top[y]]) x=fa[top[x]]; else y=fa[top[y]]; return dep[x]<dep[y] ? x : y; } #define lp p<<1 #define rp p<<1|1 void build(int p, int L, int R) { l[p]=L, r[p]=R; if (L==R) { s[p]=a[rnk[L]]; return; } int mid=L+R>>1; build(lp, L, mid); build(rp, mid+1, R); s[p]=(s[lp]+s[rp])%mod; } void pushdown(int p) { s[lp]=(s[lp]+(r[lp]-l[lp]+1)*t[p])%mod; s[rp]=(s[rp]+(r[rp]-l[rp]+1)*t[p])%mod; t[lp]=(t[lp]+t[p])%mod, t[rp]=(t[rp]+t[p])%mod, t[p]=0; } void change(int p, int L, int R, int v) { if (L<=l[p] && r[p]<=R) { t[p]=(t[p]+v)%mod; s[p]=(s[p]+(r[p]-l[p]+1)*v)%mod; return; } pushdown(p); int mid=l[p]+r[p]>>1; if (L<=mid) change(lp, L, R, v); if (R>mid) change(rp, L, R, v); s[p]=(s[lp]+s[rp])%mod; } int query(int p, int L, int R) { if (L<=l[p] && r[p]<=R) return s[p]; pushdown(p); int mid=l[p]+r[p]>>1, r=0; if (L<=mid) r=(r+query(lp, L, R))%mod; if (R>mid) r=(r+query(rp, L, R))%mod; return r; } void change_tree(int x, int v) { change(1, dfn[x], dfn[x]+siz[x]-1, v); } int query_tree(int x) { return query(1, dfn[x], dfn[x]+siz[x]-1); } void change_chain(int x, int y, int z) { int fx=top[x], fy=top[y]; while (fx!=fy) { if (dep[fx]>=dep[fy]) change(1, dfn[fx], dfn[x], z), x=fa[fx]; else change(1, dfn[fy], dfn[y], z), y=fa[fy]; fx=top[x], fy=top[y]; } change(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), z); } int query_chain(int x, int y) { int res=0, fx=top[x], fy=top[y]; while (fx!=fy) { if (dep[fx]>=dep[fy]) res=(res+query(1, dfn[fx], dfn[x]))%mod, x=fa[fx]; else res=(res+query(1, dfn[fy], dfn[y]))%mod, y=fa[fy]; fx=top[x], fy=top[y]; } res=(res+query(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y])))%mod; return res; } signed main() { n=read(), m=read(), rt=read(), mod=read(); for (int i=1; i<=n; i++) a[i]=read(); for (int i=1; i<n; i++) { int x=read(), y=read(); e[x].push_back(y); e[y].push_back(x); } dfs1(rt); dfs2(rt, rt); build(1, 1, n); while (m--) { int opt=read(); if (opt==1) { int x=read(), y=read(), z=read();; change_chain(x, y, z); } else if (opt==2) { int x=read(), y=read(); printf("%lld\n", query_chain(x, y)); } else if (opt==3) { int x=read(), z=read(); change_tree(x, z); } else { int x=read(); printf("%lld\n", query_tree(x)); } } return 0; } ``` --- ### [Luogu P1505 [国家集训队]旅游](https://www.luogu.com.cn/problem/P1505) 题意自己看吧 显然也是一道板子题，操作变多了一些， 最大值最小值线段树都可以维护。 因为题目里操作的是边，我们可以把边权记录到点上，把每个点的点权设为他到父亲的边权，这样每次修改或查询的时候不能算它们 lca 的权值，其它的都要算上，这样在做完链操作后靠上面的节点是 lca ，从它后一位开始做即可。 修改后代码如下 ```c++ if (dfn[x]>dfn[y]) res=min(res, ask_min(1, dfn[y]+1, dfn[x])); else if (dfn[y]>dfn[x]) res=min(res, ask_min(1, dfn[x]+1, dfn[y])); ``` 完整代码： ```c++ #include <cstdio> #include <cctype> #include <utility> #include <vector> #define lp p<<1 #define rp p<<1|1 using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=1e6+10; int n, m, v[N], X[N], Y[N], sz[N], fa[N], son[N], top[N], dfn[N], dep[N], dfncnt; int l[N], r[N], s[N], mn[N], mx[N], t[N]; vector<pair<int, int> >e[N]; void dfs1(int x) { sz[x]=1; dep[x]=dep[fa[x]]+1; for (int i=0; i<e[x].size(); i++) { int y=e[x][i].first; if (y==fa[x]) continue; fa[y]=x; dfs1(y); sz[x]+=sz[y]; if (sz[y]>sz[son[x]]) son[x]=y; } } void dfs2(int x, int t) { top[x]=t; dfn[x]=++dfncnt; if (!son[x]) return; dfs2(son[x], t); for (int i=0; i<e[x].size(); i++) { int y=e[x][i].first; if (y==fa[x] || y==son[x]) continue; dfs2(y, y); } } void build(int p, int L, int R) { l[p]=L, r[p]=R; if (L==R) return s[p]=mx[p]=mn[p]=v[L], void(); int mid=L+R>>1; build(lp, L, mid); build(rp, mid+1, R); s[p]=s[lp]+s[rp]; mx[p]=max(mx[lp], mx[rp]); mn[p]=min(mn[lp], mn[rp]); } void pushdown(int p) { if (!t[p]) return; t[lp]^=1; s[lp]=-s[lp]; swap(mx[lp], mn[lp]); mx[lp]=-mx[lp]; mn[lp]=-mn[lp]; t[rp]^=1; s[rp]=-s[rp]; swap(mx[rp], mn[rp]); mx[rp]=-mx[rp]; mn[rp]=-mn[rp]; t[p]=0; } void qufan(int p, int L, int R) { pushdown(p); if (L<=l[p] && r[p]<=R) { s[p]=-s[p]; swap(mx[p], mn[p]); mx[p]=-mx[p]; mn[p]=-mn[p]; t[p]=1; return; } int mid=l[p]+r[p]>>1; if (L<=mid) qufan(lp, L, R); if (R>mid) qufan(rp, L, R); s[p]=s[lp]+s[rp]; mx[p]=max(mx[lp], mx[rp]); mn[p]=min(mn[lp], mn[rp]); } void change(int p, int x, int k) { pushdown(p); if (l[p]==r[p]) return s[p]=mx[p]=mn[p]=k, void(); int mid=l[p]+r[p]>>1; if (x<=mid) change(lp, x, k); else change(rp, x, k); s[p]=s[lp]+s[rp]; mx[p]=max(mx[lp], mx[rp]); mn[p]=min(mn[lp], mn[rp]); } int ask_sum(int p, int L, int R) { pushdown(p); if (L<=l[p] && r[p]<=R) return s[p]; int mid=l[p]+r[p]>>1, sum=0; if (L<=mid) sum+=ask_sum(lp, L, R); if (R>mid) sum+=ask_sum(rp, L, R); return sum; } int ask_min(int p, int L, int R) { pushdown(p); if (L<=l[p] && r[p]<=R) return mn[p]; int mid=l[p]+r[p]>>1, res=2e9; if (L<=mid) res=min(res, ask_min(lp, L, R)); if (R>mid) res=min(res, ask_min(rp, L, R)); return res; } int ask_max(int p, int L, int R) { pushdown(p); if (L<=l[p] && r[p]<=R) return mx[p]; int mid=l[p]+r[p]>>1, res=-2e9; if (L<=mid) res=max(res, ask_max(lp, L, R)); if (R>mid) res=max(res, ask_max(rp, L, R)); return res; } void qufan_chain(int x, int y) { int fx=top[x], fy=top[y]; while (fx!=fy) { if (dep[fx]>=dep[fy]) qufan(1, dfn[fx], dfn[x]), x=fa[fx]; else qufan(1, dfn[fy], dfn[y]), y=fa[fy]; fx=top[x], fy=top[y]; } if (dfn[x]>dfn[y]) qufan(1, dfn[y]+1, dfn[x]); else if (dfn[y]>dfn[x]) qufan(1, dfn[x]+1, dfn[y]); } int sum_chain(int x, int y) { int fx=top[x], fy=top[y], res=0; while (fx!=fy) { if (dep[fx]>=dep[fy]) res+=ask_sum(1, dfn[fx], dfn[x]), x=fa[fx]; else res+=ask_sum(1, dfn[fy], dfn[y]), y=fa[fy]; fx=top[x], fy=top[y]; } if (dfn[x]>dfn[y]) res+=ask_sum(1, dfn[y]+1, dfn[x]); else if (dfn[y]>dfn[x]) res+=ask_sum(1, dfn[x]+1, dfn[y]); return res; } int max_chain(int x, int y) { int fx=top[x], fy=top[y], res=-2e9; while (fx!=fy) { if (dep[fx]>=dep[fy]) res=max(res, ask_max(1, dfn[fx], dfn[x])), x=fa[fx]; else res=max(res, ask_max(1, dfn[fy], dfn[y])), y=fa[fy]; fx=top[x], fy=top[y]; } if (dfn[x]>dfn[y]) res=max(res, ask_max(1, dfn[y]+1, dfn[x])); else if (dfn[y]>dfn[x]) res=max(res, ask_max(1, dfn[x]+1, dfn[y])); return res; } int min_chain(int x, int y) { int fx=top[x], fy=top[y], res=2e9; while (fx!=fy) { if (dep[fx]>=dep[fy]) res=min(res, ask_min(1, dfn[fx], dfn[x])), x=fa[fx]; else res=min(res, ask_min(1, dfn[fy], dfn[y])), y=fa[fy]; fx=top[x], fy=top[y]; } if (dfn[x]>dfn[y]) res=min(res, ask_min(1, dfn[y]+1, dfn[x])); else if (dfn[y]>dfn[x]) res=min(res, ask_min(1, dfn[x]+1, dfn[y])); return res; } int main() { int n=read(); for (int i=1; i<n; i++) { int x=read()+1, y=read()+1, z=read(); e[x].push_back(make_pair(y, z)); e[y].push_back(make_pair(x, z)); X[i]=x; Y[i]=y; } dfs1(1); dfs2(1, 1); for (int x=1; x<=n; x++) { for (int i=0; i<e[x].size(); i++) { int y=e[x][i].first; if (fa[x]==y) v[dfn[x]]=e[x][i].second; } } build(1, 1, n); int m=read(); while (m--) { char s[10]; scanf("%s", s+1); int x=read(), y=read(); if (s[1]=='C') { int t; if (fa[X[x]]==Y[x]) t=X[x]; else t=Y[x]; change(1, dfn[t], y); } if (s[1]=='N') qufan_chain(x+1, y+1); if (s[1]=='S') printf("%d\n", sum_chain(x+1, y+1)); if (s[1]=='M' && s[2]=='A') printf("%d\n", max_chain(x+1, y+1)); if (s[1]=='M' && s[2]=='I') printf("%d\n", min_chain(x+1, y+1)); } return 0; } ``` ## 参考 1. [OI-wiki](https://oi-wiki.org/graph/hld/) 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏