重链剖分学习笔记（基本完成）

[**cnblogs**](https://www.cnblogs.com/MnZnOIerLzy/p/17812912.html) # 前言 树链剖分（简称树剖）是一种将树剖分成若干链维护信息解决问题的思想。本文讲的是其中的**重链剖分**，着重介绍较为基础的内容，旨在帮助初学者更好地理解并掌握。 **[附题单](https://www.luogu.com.cn/training/401651)** # 求 LCA 定义（斜杠表示本文中对其可能有多种表示方法）： - $d_u/dep_u$ 为点 $u$ 的深度（到根的**边**数）。 - $sz_u/siz_u$ 为以 $u$ 为根的子树大小。 - $f_u/fa_u$ 为点 $u$ 的父亲。 - $h_u/hvy_u/hea_u/hson_u$ 为点 $u$ 的一个儿子 $v$ 满足 $sz_v>\dfrac{sz_u}{2}$，称为**重儿子**，一个点除重儿子外的儿子称为**轻儿子**。显然，一个点**至多只有一个重儿子**。 - **重边**为点 $u$ 与 $h_u$ 之间的连边（如图中的$\bf\color{red}红$边）。**轻边**为树中除重边以外的边（$\bf\color{blue}蓝$边）：  - **重链**为由**连续的重边**组成的**极长链**。特别地，若一个点没有重边与之相连，则**也称这个点为重链**。 - $t_u/top_u$ 为 $u$ 所在重链中，深度**最小**的点，称之为**链头**。 upd：可以定义为**子树大小最大的儿子**。核心思想都是使得走一条连向父亲的轻边子树大小至少乘 $2$。 可以通过 DFS 求出上述量： ```cpp void dfs1(int u,int fa){//求 sz[u]，d[u]，f[u]。 sz[u]=1; for(int v:g[u]){ if(v^fa){ d[v]=d[u]+1; dfs1(v,f[v]=u); sz[u]+=sz[v]; } } } void dfs2(int u,int fa){//求 h[u]，t[u]。 for(int v:g[u]){ if(v^fa){ if((sz[v]<<1)>sz[u]){ t[h[u]=v]=t[u]; }else{ t[v]=v; } dfs2(v,u); } } } ``` 应用：[**洛谷 P3379 【模板】最近公共祖先（LCA）**](https://www.luogu.com.cn/problem/P3379 "**洛谷 P3379 【模板】最近公共祖先（LCA）**") > - 给出 $n$ 个点的有根树，根为 $s$。$m$ 次询问，每次询问点 $a,b$ 的最近公共祖先。 > > - $n,m\le 5\times 10^5$。 考虑使用树链剖分。先看求 LCA 的代码： ```cpp int lca(int x,int y){ while(t[x]^t[y]){ if(d[t[x]]<d[t[y]]){ swap(x,y); } x=f[t[x]]; } if(d[x]>d[y]){ swap(x,y); } return x; } ``` 该代码求解 LCA 的过程用两句话来讲就是： - 若 $x,y$ 在**不同重链**中，选取**链头深度较大**的点，让其跳过链头到达**链头的父亲**。 - 若 $x,y$ 在**同一重链**中，**深度小的点即为 LCA**。 **证明** 定义： - $x\leftarrow f_{t_x}$ 为**跳链操作**，显然一个点能进行跳链操作**必须满足其链头深度较大**。**特殊地，维护同一重链上的信息也称为跳链操作（方便后文表达）**。 - $LCA(x,y)$ 为 $x,y$ 的 LCA，简称 LCA。 首先，最后跳到的节点**一定是公共祖先**，只需要证明它**深度最大**，即**不是 LCA 的祖先**。 考虑反证，假设某次跳链操作 $x$ 越过了 LCA（设到达 LCA 的某个祖先 $z$），如图：  说明 LCA 到 $x$ 之间的边全部是**重边**（$\bf \color{red}红$边）。则 LCA 向自己儿子中 $y$ 所在子树的根的连边为**轻边**（$\bf\color{orange}橙$边）：  则 $d_{t_x}\le d_{LCA(x,y)}$，$d_{t_y}> d_{LCA(x,y)}$，$d_{t_y}>d_{t_x}$，这与 $x$ 能进行跳链操作相矛盾。因此**跳到的一定是 LCA**，原命题得证。 接下来分析复杂度。因为 **$t_x$ 到 $f_{t_x}$ 的那条边一定是轻边（不然 $f_{t_x}$ 也在重链上，$t_x$ 就不是重链上深度最小的点了）**。根据轻边的性质，跳一条轻边**所在子树大小至少乘 $2$（同一重链上的情况作为常数忽略）**。所以跳链操作的次数是 $\mathcal{O}(\log n)$ 级别的，因此单组询问也是 $\mathcal{O}(\log n)$ 级别的。 所以，我们得到了一个时间复杂度为 $\mathcal{O}(m\log n)$，空间复杂度为 $\mathcal{O}(n)$ 的做法。 **[评测记录](https://www.luogu.com.cn/record/111536110 "评测记录") [代码](https://www.luogu.com.cn/paste/4mvouz2h)** # 树上问题转序列问题 **[洛谷 P3384 【模板】重链剖分/树链剖分](https://www.luogu.com.cn/problem/P3384 "洛谷 P3384 【模板】重链剖分/树链剖分")** > - 给出 $N$ 个点的有根树，根为 $R$，点有点权。有 $M$ 次操作，支持： > > - $\texttt{1 }x\texttt{ }y\texttt{ }z$，将 $x,y$ 路径上的点的点权加 $z$。 > > - $\texttt{2 }x\texttt{ }y$，求 $x,y$ 路径上的点的权值和，模 $P$。 > > - $\texttt{3 }x\texttt{ }z$，把以 $x$ 为根的子树内的点权值加 $z$。 > > - $\texttt{4 }x$，求以 $x$ 为根的子树内的点的权值和，模 $P$。 > > - $N,M\le 10^5$。 定义： - $num_u/id_u/dfn_u$ 为点 $u$ 的 DFS 序，简称编号/时间戳。 - $st_u$ 为 DFS 序中以 $u$ 为根的子树的起始（时间戳最小）位置，$ed_u$ 为结束（时间戳最大）位置。**显然 $st_u=dfn_u$**。 首先，你是会用线段树求解[区间加区间求和](https://www.luogu.com.cn/problem/P3372 "区间加区间求和")的。其次，若只有 $\texttt{3}$，$\texttt{4}$ 操作，利用**同一子树内点的 DFS 序连续**，可以从 $R$ 开始 DFS 求出 DFS 序，然后转化为区间加区间求和。这启示着我们对于 $\texttt{1}$，$\texttt{2}$ 操作，同样将其转化为序列问题解决。回顾求解 LCA 的过程，在跳链时，我们需要维护当前链上的信息。因此，我们需要得到一种使得**重链上的点编号连续**的 DFS 序。可以通过如下的代码求出： ```cpp void dfs3(int x, int fa) { sg[st[x] = num[x] = ++sg[0]] = val[x] % p; if (h[x]) { dfs3(h[x], x); } for (int i : g[x]) { if ((i ^ fa) && (i ^ h[x])) { dfs3(i, x); } } ed[x] = sg[0]; } ``` 在这个代码中，**若出现连续的重边，就会优先 DFS 重儿子，使当前重链的下一个点的编号为当前点编号加 $1$，从而达到编号连续的目的**。 为什么这样能够不重不漏地维护信息呢~~（笔者想硬胡一个理性理解，您要是觉得混淆还是跳过这部分，毕竟是个常识）~~？ - 对于最终跳到同重链上的两个点，会维护它们之间的信息（代码里可以实现）。 - 对于在重链上的点，跳到其重链之前会先维护它以下的信息，跳过它后会维护它以上的信息，因此**不会重复**。跳到当前重链时，这个点被包含在重链内，在线段树中维护的区间包括了它，因此**不会漏**。 之后就是区间问题了。由于跳链操作总数为 $\mathcal{O}(M\log N)$ 级别，每次跳链要在其对应的 DFS 序区间内进行线段树操作（一次为 $\mathcal{O}(\log N)$），因此时间复杂度为 $\mathcal{O}(M\log^2 N)$，空间复杂度为 $\mathcal{O}(N)$。 **[评测记录](https://www.luogu.com.cn/record/86040325 "评测记录") [代码](https://www.luogu.com.cn/paste/8qjdyz2p)** # 边转点技巧 **[洛谷 P4114 Qtree1](https://www.luogu.com.cn/problem/P4114 "洛谷 P4114 Qtree1")** > - 给出 $n$ 个点的树，边有边权，支持三种操作： > > - $\texttt{CHANGE }i\texttt{ }t$，将输入的第 $i$ 条边的边权改为 $t$。 > > - $\texttt{QUERY }a\texttt{ }b$，查询 $a,b$ 两点路径上最大的边权。 > > - $\texttt{DONE}$，结束程序。 > > - $n\le 10^5$，操作数不超过 $3\times 10^5$。 对于一棵树而言，**儿子向父亲的连边一定是唯一的**。因此，边转点的技巧就在于**将点的权值设置为与父亲连边的边权**。如图，$\bf\color{red}红$字表示边权，$\bf\color{green}绿$字表示点权。根暂时不去管，后面会解释。  仍旧正常跳链查询，但是当 $x,y$ 两点跳到同一重链上的时候：  这一段链维护的信息实际上是 **$x$ 的重儿子到 $y$** 这一段区间。因此跳链的代码要写成这样： ```cpp inline int answer(int x, int y) { if (x == y) {//没有边。 return 0; } int ans = -1e9; while (t[x] ^ t[y]) { if (d[t[x]] < d[t[y]]) { swap(x, y); } ans = max(ans, query(1, 1, n, dfn[t[x]], dfn[x]));//仍然正常维护链上信息，相当于维护 x 到 f[t[x]] 的边。 x = f[t[x]]; } if (x == y) {//相等时，说明 x 到 LCA、y 到 LCA 的链都已经维护好（可以结合上图理解）。 return ans; } if (d[x] > d[y]) {//先令 y 为那个相同重链上不是 LCA 的点了。 swap(x, y); } return max(ans, query(1, 1, n, dfn[x] + 1, dfn[y]));//重儿子到 y。 } ``` 回过头来解释一下为什么不用管根，因为若根作为 LCA，并且 $x,y$ 两点同时跳到，会**直接返回**。若根和 $y$ 之间还有边，会**从根的重儿子开始维护，不会涉及到根**。因此不用管根。 修改就是单点修改那条边两端深度较大的节点，因为那条边的信息存在儿子上了。 记 $m$ 为操作数。时间复杂度为 $\mathcal{O}(m\log^2 n)$，空间复杂度为 $\mathcal{O}(n)$。 **[评测记录](https://www.luogu.com.cn/record/86138284 "评测记录") [代码](https://www.luogu.com.cn/paste/nrh1lacd)** **习题：** **Ⅰ - [ABC294G Distance Queries on a Tree](https://atcoder.jp/contests/abc294/tasks/abc294_g "ABC294G Distance Queries on a Tree")** **[洛谷链接](https://www.luogu.com.cn/problem/solution/AT_abc294_g "洛谷链接")** > - 给 $n$ 个点的树，$Q$ 次操作： > > - $\texttt{1 }i\texttt{ }w$，将第 $i$ 条边边权改为 $w$。 > > - $\texttt{2 }x\texttt{ }y$，查询 $x,y$ 之间路径的权值和。 > > - $n,Q\le 2\times 10^5$。 ~~唯一赛时会的 G。~~ 运用边转点技巧，由于只有单点修改，并且是可差分信息，套上树状数组维护即可。 时间复杂度为 $\mathcal{O}(Q\log^2 n)$，空间复杂度为 $\mathcal{O}(n)$。 **[评测记录（含代码）](https://atcoder.jp/contests/abc294/submissions/39870783 "评测记录（含代码）")** # 维护“存在性信息”小优化 **[洛谷 P3398 仓鼠找 sugar](https://www.luogu.com.cn/problem/P3398 "洛谷 P3398 仓鼠找 sugar")** > - 给出 $n$ 个点的树，$q$ 次询问 $a,b$ 之间的路径和 $c,d$ 之间的路径有没有公共点。 > > - $n,q\le 10^5$。 这是一种极其无脑的做法，就是码量比较大。我们直接将 $a,b$ 路径上的点全**推平成 $1$**，再查询 $c,d$ 路径上有没有 $1$ 就行了，具体方法是维护**区间或和**。注意到只要有一个 $1$ 即可，因此当查到 $1$ 的时候，直接返回即可。 维护这种**存在性**的信息，都可以采用类似的技巧优化。 时间复杂度 $\mathcal{O}(q\log^2 n)$，空间复杂度 $\mathcal{O}(n)$。但是经过剪枝，甚至跑得比部分 $\mathcal{O}(q\log n)$ 的代码还要快。 **[评测记录](https://www.luogu.com.cn/record/102955516 "评测记录") [代码](https://www.luogu.com.cn/paste/qbk8cgtx)** **习题** **Ⅰ - [洛谷 P3950 部落冲突](https://www.luogu.com.cn/problem/P3950 "洛谷 P3950 部落冲突")** > - 给出 $n$ 个点的树，$m$ 次操作，有以下几种： > > - $\texttt{Q }p\texttt{ }q$，查询 $p$ 能否到达 $q$。 > > - $\texttt{C }p\texttt{ }q$，断掉 $p,q$ 之间的边，保证 $p,q$ 相邻。 > > - $\texttt{U }x$，对于第 $x$ 次 $\texttt{C}$ 操作，恢复那条边。 > > - $n,m\le 3\times 10^5$。 先边转点，然后用 $1$ 表示边是好的，$0$ 表示断开。显然 $p$ 能到 $q$ 必须路径上的边全是 $1$。维护**区间与和**，支持单点修改，同样可以类似剪枝。 时间复杂度 $\mathcal{O}(m\log^2 n)$，空间复杂度 $\mathcal{O}(n)$。 **[评测记录](https://www.luogu.com.cn/record/107577310 "评测记录") [代码](https://www.luogu.com.cn/paste/twaiupof)** # 结合“颜色限制” **[洛谷 P3313 [SDOI2014]旅行](https://www.luogu.com.cn/problem/P3313 "洛谷 P3313 [SDOI2014]旅行")** > - 给出一棵 $N$ 个点的树，点 $i$ 有权值 $W_i$ 和颜色 $C_i$，有 $Q$ 次操作，分为以下类型： > > - $\texttt{CC }x\texttt{ }c$，执行 $C_x\leftarrow c$。 > > - $\texttt{CW }x\texttt{ }w$，执行 $W_x\leftarrow w$。 > > - $\texttt{QS }x\texttt{ }y$，查询点 $x,y$ 路径上，$C_i=C_x$ 的点 $i$ 的权值和，保证 $C_x=C_y$。 > > - $\texttt{QM }x\texttt{ }y$，查询点 $x,y$ 路径上，$C_i=C_x$ 的点 $i$ 权值的最大值，保证 $C_x=C_y$。 > > - $N,Q\le 10^5$，$1\le C_i\le 10^5$。 如果没有颜色的限制就是树剖板子。加上颜色限制后，考虑对每一种颜色在树剖后的序列上维护线段树，然后查询就是跳链时在 $C_x$ 那种颜色的线段树上查询。发现这样空间无法接受，于是考虑动态开点，**记录每种颜色的根节点**。 $\texttt{CW}$ 操作就是在对应的线段树上直接改权值，$\texttt{CC}$ 操作相当于从当前颜色的线段树中删掉并在新颜色的线段树上修改。删掉可以直接置 $0$，因为这样不会产生贡献，也可以用垃圾桶技巧，但**不建议用指针中的 `delete`**，会有玄学错误。 时间复杂度为 $\mathcal{O}(Q\log^2 N)$，空间复杂度为 $\mathcal{O}(Q\log N)$。 **[评测记录](https://www.luogu.com.cn/record/112058863 "评测记录") [代码](https://www.luogu.com.cn/paste/xez42ayd)** **习题** **Ⅰ - [洛谷 P5838 [USACO19DEC]Milk Visits G](https://www.luogu.com.cn/problem/P5838 "洛谷 P5838 [USACO19DEC]Milk Visits G")** 双倍经验：[SP11985 GOT - Gao on a tree](https://www.luogu.com.cn/problem/SP11985 "SP11985 GOT - Gao on a tree")。 > - 有一棵 $N$ 个节点的树，第 $i$ 个节点有颜色 $T_i$，$M$ 次询问，每次询问点 $A,B$ 路径上是否存在颜色为 $C$ 的节点。 > > - $N,M\le 10^5$，$1\le T_i,C\le n$。 每一种颜色分别在树链剖分后的序列上维护线动态开点线段树，将每个点在自己颜色的动态开点线段树上置 $1$，维护**区间或和**。跳链时在那种颜色对应的线段树上查询，可以使用“维护‘存在性信息’小优化”的技巧剪枝，结果为 $1$ 说明存在，为 $0$ 不存在。 时间复杂度为 $\mathcal{O}(M\log^2 N)$，空间复杂度为 $\mathcal{O}(N\log N)$。 **[评测记录](https://www.luogu.com.cn/record/112062761 "评测记录") [代码](https://www.luogu.com.cn/paste/ekf7jthe)** **Ⅱ - [ABC133F Colorful Tree](https://atcoder.jp/contests/abc133/tasks/abc133_f "ABC133F Colorful Tree")** **[洛谷链接](https://www.luogu.com.cn/problem/AT_abc133_f "洛谷链接")** > - 给出 $N$ 个节点的树，每条边有颜色、边权。处理 $Q$ 个询问，第 $i$ 次询问给出 $x_i,y_i,u_i,v_i$，表示先将所有颜色为 $x_i$ 的边边权变成 $y_i$，再求出 $u_i$ 到 $v_i$ 的路径边权和。**询问之间相互独立，即不会真的修改**。 > > - $N,Q\le 10^5$。 首先，路径上的边修改后才会影响答案。考虑树剖，先边转点。信息又和颜色有关，同样使用动态开点技巧在树剖后的序列上对每种颜色维护线段树，记录当前区间内有效边的个数 $tot$ 以及有效边的边权和 $sum$。同时维护前缀和。 跳链时，先用前缀和查询原边权和，再在线段树上查询该区间的信息，记查询到的和为 $a$，个数为 $b$。则要**将 $a$ 那一部分的贡献换成 $b\times y_i$**，对应的答案加上 $b\times y_i-a$。特判颜色不存在的情况。 时间复杂度为 $\mathcal{O}(Q\log^2 N)$，空间复杂度为 $\mathcal{O}(N)$。 **[评测记录（含代码）](https://atcoder.jp/contests/abc133/submissions/42275163 "评测记录")** **Ⅲ - [UVA12424 Answering Queries on a Tree](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=279&page=show_problem&problem=3855 "UVA12424 Answering Queries on a Tree")** [**洛谷题目链接**](https://www.luogu.com.cn/problem/UVA12424 "**洛谷题目链接**") [**PDF 题面** ](https://onlinejudge.org/external/124/p12424.pdf "**PDF 题面** ") > - 有 $n$ 个节点的树。第 $i$ 个节点颜色为 $C_i$。有 $m$ 次操作： > > - $\texttt{0 }u\texttt{ }c$：把 $C_u$ 改为 $c$。 > > - $\texttt{1 }u\texttt{ }v$：询问 $u,v$ 两点路径之间出现最多的颜色次数。 > > - $T$ 组数据，$1\le T,C_i,c\le 10$，$1\le n,m\le 10^5$，$1\le u,v\le n$。 **注：相关变量名称和原题略有不同**。 这题也是关于颜色限制的题，但是只有 $10$ 种颜色，而且只有单点修改，并且是可差分信息，因此不需要动态开点线段树，开 $10$ 棵树状数组就可以了。 先边转点，再对树剖后的序列用树状数组维护每种颜色的**前缀个数**。修改时，先将原颜色中该位置上 $-1$，再在新颜色中该位置上 $+1$。然后把颜色（$C$ 数组）改为新颜色，因为下一次修改是针对这个新颜色的。 查询时，用 $ans_i$ 表示第 $i$ 种颜色出现的次数。在跳链时，枚举每种颜色并用树状数组差分查询，再加到对应的 $ans$ 上。最后输出 $ans$ 数组的最大值即可。 时间复杂度为 $\mathcal{O}(Tm\log^2n)$，空间复杂度为 $\mathcal{O}(n)$。 **[评测记录](https://www.luogu.com.cn/record/102897637 "评测记录") [代码](https://www.luogu.com.cn/paste/50fc0wkr)** **Ⅳ - [CF960H Santa's Gift](https://www.luogu.com.cn/problem/CF960H "CF960H Santa's Gift")** **[CF](https://codeforces.com/contest/960/problem/H "CF")** **注：为了避免混淆，修改了部分变量的名称**。 > - 给出 $n$ 个点的有根树，$m$ 种颜色，点 $i$ 有颜色 $a_i$，颜色 $i$ 有权值 $b_i$。维护两种操作，共 $q$ 次： > - $\texttt{1 }x\text{ }y$，将 $a_x\leftarrow y$。 > > - $\texttt{2 }x$，从树中等概率选取一个点 $i$，得到 $(S_i\times b_x-C)^2$ 的价值。求期望价值。其中 $S_i$ 表示以 $i$ 为根的子树中颜色为 $x$ 的节点数。$C$ 是给定的常数。 > - $n,m\le 5\times 10^4$。 先写出答案的表达式： $$\begin{aligned}\dfrac{\sum_{i=1}^n(S_i\times b_x-C)^2}{n}&=\dfrac{\sum_{i=1}^n(b_x^2S_i^2-2b_xCS_i+C^2)}{n}\\&=\dfrac{b_x^2\sum_{i=1}^n S_i^2-2b_xC\sum_{i=1}^nS_i+nC^2}{n}\end{aligned}$$ 考虑维护每种颜色的 $S_i$，套路树剖再动态开点线段树。操作 $\texttt{1}$ 相当于对颜色 $a_x$ 将根到 $x$ 路径上的 $S_i$ 减 $1$，对于颜色 $y$ 将这些 $S_i$ 加 $1$。这个修改区间含根节点很友好，不需要正常跳链，直接从 $x$ 跳到根就好了。 线段树的节点要维护平方和以及和，简单讲一下平方和的维护： $$\begin{aligned}\sum\limits_{i=l}^r(x_i+v)^2&=\sum\limits_{i=l}^r(x_i^2+2vx_i+v^2)\\&=\sum\limits_{i=l}^rx_i^2+2v\sum\limits_{i=l}^rx_i+(r-l+1)v^2\end{aligned}$$ 就是在**原来平方和**的基础上加上 $2v$ 倍的**原来的和**，再加上 $(r-l+1)v^2$。由于是动态开点线段树不方便 pushdown，所以写了标记永久化。 对于 $\texttt{2}$ 操作，查询区间为 $[1,n]$ 也很友好，直接用那种颜色线段树的根的信息就可以了。 时空复杂度均为 $\mathcal{O}(m\log^2n)$，可以接受。 **[评测记录（含代码）](https://codeforces.com/contest/960/submission/211670722 "评测记录")** **Ⅴ - [CF463E Caisa and Tree](https://www.luogu.com.cn/problem/CF463E)** > - 给出 $n$ 个点以 $1$ 为根的树，点 $u$ 有点权 $a_u$。$m$ 次操作，两种类型： > > - $1\texttt{ }u$，查询点 $u$ 的一个**最近**祖先 $v$，满足 $\gcd(a_u,a_v)>1$，没有输出 $-1$。 > > - $2\texttt{ }u\texttt{ }d$，将 $a_u\leftarrow d$。 > > - $n,m\le 10^5$，$a_u\le 2\times 10^6$。 「保证 $2$ 操作的数量不超过 $50$」的限制和 $10$ 秒的时限太不牛了。让我们去掉这个限制并将时限改为 $2$ 秒，再考虑怎么做。 看到单点修改和路径查询，容易想到树链剖分。考虑到 $\gcd(a_u,a_v)>1$ 本质上是 $a_u,a_v$ 有着共同的质因数，所以要先用欧拉筛筛出 $2\times 10^6$ 内的质数。然后可以枚举这个质因数，分别查询有该质因数的最近祖先，再从其中选出最近的即可。 由于根到某个点路径的 $dfn$ 序是递增的，考虑通过求最大的 $dfn$ 序来找到最近祖先。具体地，对每种质数维护一个 `set`，里面有序存放点权有该质因数的点的 $dfn$ 序。查询某种质因数时，在跳链的过程中通过 `lower_bound` 和 `upper_bound` 二分找到不超过当前点 $u$ 的最大 $dfn$ 序（如果 $u$ 为初始点则是严格小于，因为自己不能选），若该值 $\ge dfn_{top_u}$，说明该值对应的点在当前重链上，直接返回即可。 对于修改操作，相当于在 $a_u$ 的质因数的 `set` 中删除 $dfn_u$，在 $y$ 的质因数的 `set` 中插入 $dfn_u$。 乍一看分解质因数很暴力，但是我们可以在欧拉筛的时候处理每个数 $i$ 的最小质因数 $pre_i$，分解质因数的时候，设当前数为 $x$，则分解一个 $pre_{x}$ 出来，再令 $x\leftarrow \dfrac{x}{pre_{x}}$。由于质数 $\ge 2$，因此除以 $pre_x$ 的操作**至多进行 $\log x$ 次**，意味着我们完成了在 $\mathcal{O}(\log x)$ 的时间复杂度内分解质因数。而且，$2\times 10^6$ 内的数**本质不同的质因数个数不超过 $7$**，考虑 $2\times 3\times 5\times 7\times 11\times 13\times 17\times 19=9699690$，而我们对于同一个质因数只需要进行一次跳链查询/修改 `set`，因此单次操作跳链查询/修改 `set` 次数是常数级别。 设值域为 $V$，最终的时间复杂度为 $\mathcal{O}(m\log^2 n)$，空间复杂度为 $\mathcal{O}(|V|)$。 [**评测记录（含代码）**](https://codeforces.com/contest/463/submission/222000856 "**评测记录**") **Ⅵ - [洛谷 P6088 [JSOI2015] 字符串树](https://www.luogu.com.cn/problem/P6088)** > - 给出 $n$ 个点的树，边上有字符串 $s$，$q$ 次询问 $u,v$ 两点路径上有多少边的字符串以字符串 $t$ 为前缀。 > > - $n,q\le 10^5$，$|s_i|\le 10$。 注意到 $|s_i|\le 10$，即本质不同的前缀不会超过 $10^6$ 种。于是先边转点，然后把前缀看成颜色，运用本节的套路，有两种方法： - **【方法一】** 对每种字符串建立动态开点线段树，线段树上的区间维护对应的 $dfn$ 序区间内该前缀的出现次数。跳链时在对应前缀的线段树上查询。 时间复杂度为 $\mathcal{O}(q\log ^2 n)$，空间复杂度为 $\mathcal{O}\left(\left(\sum\limits_{i=1}^ns_i\right)\times \log n\right)$。 - **【方法二】** 对每种前缀开一个 `vector`，按从小到大的顺序存放具有该前缀节点的 $dfn$ 序。跳链时，设当前跳到点 $u$，二分出 $l$ 表示第一个大于等于 $dfn_{top_u}$ 的值的位置，$r$ 表示最后一个不超过 $dfn_u$ 的位置，则该重链的贡献为 $r-l+1$。 时间复杂度为 $\mathcal{O}(q\log^2 n)$，空间复杂度为 $\mathcal{O}\left(\sum\limits_{i=1}^ns_i\right)$。 相比之下，【方法一】空间更劣，常数更大，但是可以支持更多的修改操作。【方法二】空间较优，常数较小，但是在修改方面有一定的局限性。 给的是【方法二】的代码。 **[评测记录](https://www.luogu.com.cn/record/124272144 "评测记录") [代码](https://www.luogu.com.cn/paste/zrjigmx8)** **[Ⅶ - 洛谷 P4947 PION后缀自动机](https://www.luogu.com.cn/problem/P4947)** > - 给出一棵 $n$ 个点的树，每个点上有若干字符串，有 $m$ 次操作，分为三种： > > - $\texttt{query /p }u\texttt{ }v$，查询 $u,v$ 简单路径上的边数。 > > - $\texttt{query /e }u \texttt{ }v\texttt{ *.}s$，查询 $u,v$ 简单路径上字符串 $s$ 出现了几次。 > > - $\texttt{del /e }u \texttt{ }v\texttt{ *.}s$，查询 $u,v$ 简单路径上字符串 $s$ 出现了几次，并删除这些 $s$。 > > - $n,m\le 10^5$，字符串总数 $k$ 不超过 $5\times 10^5$，字符串长度不超过 $8$。 $\texttt{query /p}$ 操作比较简单，答案为 $dep_u+dep_v-2\times dep_{\text{LCA}(u,v)}$。考虑解决剩下两个操作。 字符串的种数很少，考虑使用 [P5838](https://www.luogu.com.cn/problem/P5838 "P5838") 的套路，有两种方法： - **【方法一】** 对每种字符串维护一棵动态开点线段树，线段树的节点维护对应 $dfn$ 序区间内该字符串的出现次数。 - 对于 $\texttt{query /e}$ 操作，跳链时在对应的线段树上查询当前重链的贡献。 - 对于 $\texttt{del /e}$ 操作，则先做一遍 $\texttt{query /e}$ 操作，然后再进行删除。删除的时候，在跳链时将当前重链对应的 $dfn$ 区间推平成 $0$。 时间复杂度为 $\mathcal{O}(m\log^2 n)$，空间复杂度为 $\mathcal{O}(k\log n)$。 - **【方法二】** 对每种字符串维护一棵平衡树（这里使用 `__gnu_pbds::tree`），有序存放有该字符的点的 $dfn$ 序，注意可能会重复，所以元素类型为 `pair`，`second` 的作用是区分同一个点的两个相同字符串。 - 对于 $\texttt{query /e}$ 操作，设当前在点 $u$，跳链时使用 `order_of_key` 找到在 $[1,dfn_{top_u})$ 和 $[1,dfn_u]$ 中的值个数，相减即为当前重链上该字符串的出现次数。 - 对于 $\texttt{del /e}$ 操作，同样先做一遍 $\texttt{query /e}$ 操作，然后再进行删除。删除的时候，使用 `lower_bound` 找到第一个大于等于 $dfn_{top_u}$ 的迭代器 $l$ 和第一个大于 $dfn_u$ 的迭代器 $r$，**暴力删除 $[l,r)$** 之间的所有迭代器。 看上去很暴力，但是一开始插入了 $k$ 个元素，一个元素只能被删除一次，因此时间复杂度为 $\mathcal{O}(m\log^2 n)$，空间复杂度为 $\mathcal{O}(k+n)$。 给的是【方法二】的代码。笔者因为看到 [P7735](https://www.luogu.com.cn/problem/P7735 "P7735") 的一种新写法，即求出 $\texttt{LCA}(u,v)$ 后分别算 $u\rightsquigarrow \text{LCA}(u,v)$ 和 $v\rightsquigarrow \text{LCA}(u,v)$ 的信息，以为会更好写，结果那种写法会算重 $\text{LCA}(u,v)$ 的信息。在 P7735 中单点是没有贡献的，但是这题有，于是调了很久才发现要单独减去 $\text{LCA}(u,v)$ 的贡献。因此部分代码不建议读者参考，还是建议读者去参考本文“树上问题转序列问题”中提到的跳链写法。 **[评测记录](https://www.luogu.com.cn/record/124722556 "评测记录") [代码](https://www.luogu.com.cn/paste/amygqmdd)** # 维护树上子段信息 **[SP6779 GSS7 - Can you answer these queries VII](https://www.luogu.com.cn/problem/SP6779 "SP6779 GSS7 - Can you answer these queries VII")** > - 给出 $N$ 个点的树，点 $i$ 有点权 $x_i$。给出 $Q$ 次操作： > > - $\texttt{1 }a\texttt{ }b$，查询 $a,b$ 路径上的最大子段和（就是路径上的点构成的连续序列的最大子段和，可以为 $0$，即空序列）。 > > - $\texttt{2 }a\texttt{ }b\texttt{ }c$，将 $a,b$ 路径上的点权值赋值成 $c$。 > > - $N,Q\le 10^5$。 首先你是会[区间最大子段和](https://www.luogu.com.cn/problem/P4513 "区间最大子段和")的，区间推平就是打懒标记，**如果为正就取整个区间，否则取空区间。** 考虑在树上怎么做，回顾区间最大子段和的过程，线段树非叶子节点的信息是由**左右儿子的信息合并起来的**。这里为了后文方便阐述，给一下合并区间信息的代码，稍微讲一下： ```cpp //ans 为合并的区间；l，r 为被合并的区间；sum 表示区间和；ret 表示区间最大子段和；lmax 表示区间最大前缀和；rmax 表示区间最大后缀和。 node merge(node l,node r){ node ans; ans.sum=l.sum+r.sum; ans.lmax=max(l.lmax,l.sum+r.lmax);//考虑信息是否横跨两个区间。 ans.rmax=max(r.rmax,r.sum+l.rmax); ans.ret=max({l.ret,r.ret,l.rmax+r.lmax}); return ans; } ``` 那么对于一棵树，我们可以**以 LCA 为界，将两边链的信息合并**，如图中$\color{red}\bf 红$色和$\color{blue}\bf蓝$色部分：  在跳到同一重链之前，类似合并重链信息即可，跳到同一重链之后，分两种情况（图中涂上$\color{red}\bf红$/$\color{blue}\bf蓝$色的链为最终跳到的同一重链）：   还有一个小细节。合并完得到的两条链是这样的：  由于合并的是**连续的序列**，因此**方向应该相同**。所以对于 $x$ 一路跳链合并成的那一段信息，要交换以下 $lmax$ 和 $rmax$，即原来的 $rmax$ 从右边到了左边变成了 $lmax$，原来的 $lmax$ 从左边到了右边变成了 $rmax$，如图中的 $\color{orange}lmax,rmax$：  剩下几种情况同理即可。 时间复杂度为 $\mathcal{O}(Q\log^2 N)$，空间复杂度为 $\mathcal{O}(N)$。 **[评测记录](https://vjudge.net/solution/43433424 "评测记录") [代码](https://www.luogu.com.cn/paste/xcet1pcz)** **习题** **Ⅰ - [洛谷 P7735 [NOI2021] 轻重边](https://www.luogu.com.cn/problem/P7735 "洛谷 P7735 [NOI2021] 轻重边")** **注：为了避免混淆，修改了原题中某些定义的名称。** > - 给出 $n$ 个点的树，树上可能会出现两种边：短边和长边。一开始所有边都是短边。有 $m$ 次操作，两种类型： > > - $\texttt{1 }a\texttt{ }b$，对于 $a,b$ 路径上的任意一点，将所有与其相连的边变成短边，再将路径上的所有边变成长边。 > > - $\texttt{2 }a\texttt{ }b$，查询 $a,b$ 路径上有多少条长边。 > > - $T$ 组数据，$T\le 3$，$n,m\le 10^5$。 **注：需要和“结合‘颜色限制’”区分，这里的颜色属于一类维护的信息，而非一种限制。** 挺诈骗，和边转点没有一点关系。 首先要对问题进行一定的转化。有结论：**钦定一开始树上所有点的颜色都是 $0$，对于第 $i$ 次 $\texttt{1}$ 操作，将这条路径的点染上颜色 $i$，则两个端点颜色相同且不为 $0$ 的边就是长边，反之为短边**。 考虑归纳证明，结论对于初始状态成立。由于**没有端点在路径上的边在操作后是不会变的**，因此只需要考虑以下几类情况： - 与路径重合的边，操作后应该是长边。由于其两端点都在路径上，被染成了相同的颜色，所以是长边，结论成立。 - 一个端点在路径上的边，操作后应该是短边。若其之前是长边，说明**之前两端点颜色都为 $j(0<j<i)$，则此时一个端点被染成了 $i$，两端点颜色不同**，是短边，结论成立；若其之前是短边，**则两个端点颜色分别为 $j,k(0\le j,k<i)$，此时无论替换哪个点的颜色为 $i$ ，两端点的颜色都是不同的**，是短边，结论成立。 证毕。 看到路径操作首先想树剖，考虑如何对树剖后的序列维护区间内**相邻的、颜色相同且不为 $0$ 的无序对数量**。在线段树节点内维护区间最左/右边的位置的颜色 $lc/rc$，区间答案 $tot$。合并区间信息就是这样： ```cpp il node merge(co node&l,co node&r){//合并左右两个区间。 node ret; ret.lc=l.lc;//左端肯定是左区间的左端。右端同理。 ret.rc=r.rc; ret.tot=l.tot+r.tot;//不跨区间的情况，子区间的答案都要算。 if(l.rc&&r.lc&&l.rc==r.lc){//跨区间，如果符合条件就算上。 ++ret.tot; } return ret; } ``` 查询就是跳链的时候合并重链信息。注意仍要想例题那样注意**最终以 LCA 为界的两条链合并时的方向**。 时间复杂度为 $\mathcal{O}(Tm\log^2n)$，空间复杂度为 $\mathcal{O}(n)$，不知为何我的代码要卡常才能过。 **[评测记录](https://www.luogu.com.cn/record/108091746 "评测记录") [代码](https://www.luogu.com.cn/paste/xs68itnz)** **Ⅱ - [洛谷 P9555 「CROI · R1」浣熊的阴阳鱼](https://www.luogu.com.cn/problem/P9555)** > - 给出 $n$ 个点的树，点有点权 $a_i(a_i\in\{0,1\})$。支持 $q$ 次操作： > > - $\texttt{1 }u$，$a_u\leftarrow \lnot a_u$。 > > - $\texttt{2 }u\texttt{ }v$，你带着一个最大大小为 $2$ 的可重集 $S$ 从 $u$ 走到 $v$，初始 $S=\varnothing$，遇到一个点 $x$，若 $\lnot a_x\in S$，则删除 $\lnot a_x$，得分 $+1$，否则将 $a_x$ 插入 $S$。求最终的得分。 > > - $n,q\le 10^5$。 看到树上修改和路径查询，首先想到树剖。我们发现 $|S|\le 2$，且 $S$ 的顺序不影响答案，因此我们可以用一个二元组 $(i,j)(0\le i\le j\le 2)$ 记录 $S$ 的状态（$0,1$ 表示放了什么元素，$2$ 表示没有元素）。为了方便表述，将 $2$ 也认为是 $S$ 内的元素，即强制 $|S|=2$。 分析一下询问，相当于已经给定了初始状态 $S=\{a_u,2\}$。再根据树剖的思想，我们要快速查询一条重链上的信息，即快速查询那条链对应的区间的信息。考虑使用线段树维护。具体地，对于线段树上的一个节点 $x$（设对应的区间为 $[l,r]$），记 $f_{x,i,j}$ 表示从 $l$ 位置开始走，**经过 $l$ 位置后** $S=\{i,j\}$，走到 $r$ 时的得分，类似地 $g_{x,i,j}$ 表示从 $r$ 走到 $l$ 的得分。还需要记录 $LtoR_{x,i,j}$ 表示从 $l$ 位置开始走，**经过 $l$ 位置后** $S=\{i,j\}$，到达 $r$ 后 $S$ 的状态，同理还有 $RtoL_{x,i,j}$ 表示从 $r$ 到达 $l$ 后 $S$ 的状态。注意，我们强调了**初始 $S$ 是经过起点后的状态**，意味着上述的 $S$ 都**已经受起点的影响**，即**统计答案的时候不再受到起点的影响（因为已经受过了）**。类似地，强调 $LtoR$ 和 $RtoL$ 是到达端点后的状态，说明信息已经受到终点的影响，因为状态的定义里保证了它受到起点的影响，所以同时保证了统计了**完整**的信息。 考虑如何合并区间信息，我们发现需要快速计算出已经到了一个区间末尾，下一步走到另一半区间开头时，$S$ 的状态，因此还需要记录 $lc_{x},rc_{x}$ 来存储 $a_l$ 和 $a_r$。所以线段树的节点是张这样的： ```cpp #define pii pair<int,int> struct node{//变量名有部分不同。 int cnt_l[3][3],cnt_r[3][3],lc,rc;//f,g,lc,rc。 pii status_l[3][3],status_r[3][3];//LtoR,RtoL。 }seg[N<<2]; ``` 然后计算状态可以通过以下的函数实现（我写的比较暴力，直接枚举 $12$ 种情况分类讨论）： ```cpp #define ppi pair<pii,int> #define mp make_pair ppi get_status(pii p,int x){//第二维表示得分增量。 if(p==mp(0,0)&&!x){ return mp(p,0); } if(p==mp(0,0)&&x){ return mp(mp(0,2),1); } if(p==mp(0,1)&&!x){ return mp(mp(0,2),1); } if(p==mp(0,1)&&x){ return mp(mp(1,2),1); } if(p==mp(0,2)&&!x){ return mp(mp(0,0),0); } if(p==mp(0,2)&&x){ return mp(mp(2,2),1); } if(p==mp(1,1)&&!x){ return mp(mp(1,2),1); } if(p==mp(1,1)&&x){ return mp(mp(1,1),0); } if(p==mp(1,2)&&!x){ return mp(mp(2,2),1); } if(p==mp(1,2)&&x){ return mp(mp(1,1),0); } return mp(mp(x,2),0);//空集就直接放。 } ``` 区间信息具体合并方法为，先从计算当前状态走到区间末尾的信息，然后计算跨过区间后的状态，以及计算跨区间这一步对得分的贡献。然后再从另一半区间，以跨区间后的状态开始走，计算得分。从当前起点走到另一个端点的状态，就是从另一半区间，以跨区间后的状态开始走，走到那个端点时的状态。代码如下: ```cpp #define fi first #define se second node merge(node l,node r){ node ret; ret.lc=l.lc; ret.rc=r.rc; for(int i=0;i<=2;++i){ for(int j=i;j<=2;++j){ ppi l_start=get_status(r.status_r[i][j],l.rc),r_start=get_status(l.status_l[i][j],r.lc); ret.cnt_l[i][j]=l.cnt_l[i][j]+r_start.se+r.cnt_l[r_start.fi.fi][r_start.fi.se]; ret.status_l[i][j]=r.status_l[r_start.fi.fi][r_start.fi.se]; ret.cnt_r[i][j]=r.cnt_r[i][j]+l_start.se+l.cnt_r[l_start.fi.fi][l_start.fi.se]; ret.status_r[i][j]=l.status_r[l_start.fi.fi][l_start.fi.se]; } } return ret; } ``` 对于长度为 $1$ 的区间，有初始化： ```cpp seg[x].lc=seg[x].rc=b[l];//b[l] 是那个点的元素值。 for(int i=0;i<=2;++i){ for(int j=i;j<=2;++j){ seg[x].cnt_l[i][j]=seg[x].cnt_r[i][j]=0;//端点已经考虑过且没有遇到新元素，对得分无贡献。 seg[x].status_l[i][j]=seg[x].status_r[i][j]=mp(i,j);//起点终点相同，受到起点的影响即受到了终点的影响。 } } ``` 那么单点修改也很好维护： ```cpp seg[x].lc^=1; seg[x].rc^=1; ``` 查询就是跳链查询。**注意合并信息的顺序**。 时间复杂度为 $\mathcal{O}(q\log ^2n)$，空间复杂度为 $\mathcal{O}(n)$。 **[评测记录](https://www.luogu.com.cn/record/121487490 "评测记录") [代码](https://www.luogu.com.cn/paste/qxv36g4f)** **Ⅲ - [P4679 [ZJOI2011] 道馆之战](https://www.luogu.com.cn/problem/P4679)** > - 给出一棵 $n$ 个点的树。每个点有 $\text{A,B}$ 两个区域，若不是障碍物，每次可以走到相邻点的相同区域，或当前点的另一个区域。 > > - $m$ 次操作，有两种类型： > > - $\texttt{Q }u\texttt{ }v$，查询从 $u$ 开始，向 $v$ 的方向走，最多能不重复地访问多少区域。 > > - $\texttt{C }u\texttt{ }s$，将 $u$ 的区域状态改成 $s$。 > > - $n\le 5\times 10^4$，$m\le 10^5$。 下文用 $0$ 区域代表 $\text{A}$ 区域，用 $1$ 区域代表 $\text{B}$ 区域。 考虑重链剖分 + 线段树。 在线段树的一个节点内，维护： - $f_{i,j}\,(i,j\in\{0,1\})$ 表示从左端点 $i$ 区域走到右端点 $j$ 区域可以踩的最多格子数。若不能走到，则状态为 $0$。 - $g_{i,j}\,(i,j\in\{0,1\})$ 表示从右端点 $i$ 区域走到左端点 $j$ 区域可以踩的最多格子数。若不能走到，则状态为 $0$。 - $a_i\,(i\in\{0,1\})$ 表示从左端点 $i$ 区域开始最多能走多远。 - $b_i\,(i\in\{0,1\})$ 表示从右端点 $i$ 区域开始最多能走多远。 - $l$ 表示左端点的地图形状。 - $r$ 表示右端点的地图形状。 信息可以这样合并，大概就是考虑是否走过区间中点，以及从哪个区域走过区间中点： ```cpp #define str string #define co const #define mst memset struct node { int f[2][2], g[2][2], a[2], b[2]; str l, r; bool e; node(str l_ = "", str r_ = "", bool e_ = 1) { l = l_; r = r_; e = e_; mst(f, 0, sof f); mst(g, 0, sof g); mst(a, 0, sof a); mst(b, 0, sof b); } node operator+(co node o) const { if (e) return o; if (o.e) return *this; node ret(l, o.r, 0); for (int i = 0; i < 2; ++i) { ret.a[i] = a[i]; ret.b[i] = o.b[i]; for (int j = 0; j < 2; ++j) { for (int k = 0; k < 2; ++k) { bool op = (r[k] == '.' && o.l[k] == '.'); if (op && f[i][k] && o.f[k][j]) ret.f[i][j] = max(ret.f[i][j], f[i][k] + o.f[k][j]); if (op && o.g[i][k] && g[k][j]) ret.g[i][j] = max(ret.g[i][j], o.g[i][k] + g[k][j]); } bool op = (r[j] == '.' && o.l[j] == '.'); if (op && f[i][j]) ret.a[i] = max(ret.a[i], f[i][j] + o.a[j]); if (op && o.g[i][j]) ret.b[i] = max(ret.b[i], o.g[i][j] + b[j]); } } return ret; } }; ``` 对于单点，有初始化： ```cpp void upd(node &o, co str s) { // 将叶子 o 的地图改成 s。 o = node(s, s, 0); for (int i = 0; i < 2; ++i) if (s[i] == '.') o.f[i][i] = o.g[i][i] = o.a[i] = o.b[i] = 1; if (s[0] =='.' && s[1] == '.') o.f[0][1] = o.f[1][0] = o.g[0][1] = o.g[1][0] = o.a[0] = o.a[1] = o.b[0] = o.b[1] = 2; } ``` 只需要支持跳链查询、单点修改即可。注意跳链查询要翻转一条链。 时间复杂度为 $\mathcal{O}(m\log ^2 n)$，空间复杂度为 $\mathcal{O}(n)$。 **[提交记录](https://www.luogu.com.cn/record/131467335) [代码](https://www.luogu.com.cn/paste/l8hxqcn4)** # 结合斐波那契数列（矩阵快速幂） **[洛谷 P5138 fibonacci](https://www.luogu.com.cn/problem/P5138 "洛谷 P5138 fibonacci")** > - 定义 $f_i$ 为斐波那契数列第 $i$ 项，满足 $f_0=0,f_1=1,f_i=f_{i-2}+f_{i-1}(i>2)$（同时定义 $i<0$ 时 $f_{i}=f_{i+2}-f_{i+1}$）。 > > - 给出以 $1$ 为根的 $N$ 个点的树，每个点初始权值为 $0$。$M$ 次操作，两种类型： > > - $\texttt{U }x\texttt{ }k$，将以 $x$ 为根子树内的所有点 $u$，将其权值加上 $f_{d_u-d_x+k}$。 > > - $\texttt{Q }x\texttt{ }y$，查询 $x,y$ 路径上点的权值和，模 $10^9+7$。 > > - $N,M\le 10^5$，$k\le 10^{18}$。 需要用到的前置知识： **Ⅰ - $i<0$ 时，$f_{i}=(-1)^{i-1}\times f_{-i}$** **证明** 考虑归纳。 - 易证当 $i=-1$，$i=-2$ 时成立。 - 假设在 $k\le i\le-2$ 时成立，则当 $i=k-1$ 时： - 若 $k$ 为奇数，则 $k+1$，$k-1$ 均为偶数，$k-2$ 为奇数。有： $$f_{k-1}=f_{k+1}-f_{k}=-f_{-k-1}-f_{-k}=-(f_{-k-1}+f_{-k})=-f_{-k+1}=(-1)^{k-2}\times f_{-(k-1)}$$ 成立。 - 若 $k$ 为偶数，则 $k+1$，$k-1$ 均为奇数，$k-2$ 为偶数。有： $$f_{k-1}=f_{k+1}-f_{k}=f_{-k-1}-(-f_{-k})=f_{-k-1}+f_{-k}=f_{-k+1}=(-1)^{k-2}\times f_{-(k-1)}$$ 成立。 证毕。 **Ⅱ - $f_{m+n}=f_{m-1}\times f_n+f_m\times f_{n+1}$** **证明** 首先 $f_{m-1}\times f_n+f_m\times f_{n+1}=f_{n-1}\times f_m+f_n\times f_{m+1}$。 考虑做差： $$\begin{aligned}f_{m-1}\times f_n+f_m\times f_{n+1}-(f_{n-1}\times f_m+f_n\times f_{m+1})&=f_m\times(f_{n+1}-f_{n-1})-f_n\times(f_{m+1}-f_{m-1})\\&=f_m\times f_n-f_n\times f_m\\&=0\end{aligned}$$ 所以上面那个式子是成立的。 先钦定 $m,n$ 为自然数。同样考虑归纳。 - 易证 $m=0$，$n=0$ 和 $m,n\in[0,1]$ 时均成立。 - 假设在 $m,n\in[1,k]$ 时成立，则当 $m,n\in[1,k+1]$ 时，在原值域上新增了三种情况： - 当 $m=k+1,n\in[1,k]$ 时： $$\begin{aligned}f_{m+n}&=f_{m+n-2}+f_{m+n-1}\\&=f_{m-1+n-1}+f_{m-1+n}\\&=f_{m-2}\times f_{n-1}+f_{m-1}\times f_n+f_{m-2}\times f_n+f_{m-1}\times f_{n+1}\\&=f_{m-2}\times (f_{n+1}-f_{n})+f_{m-1}\times f_n+f_{m-2}\times f_n+f_{m-1}\times f_{n+1}\\&=f_{m-2}\times f_{n+1}-f_{m-2}\times f_n+f_{m-1}\times f_n+f_{m-2}\times f_n+f_{m-1}\times f_{n+1}\\&=f_{m-1}\times f_n+(f_{m-2}+f_{m-1})\times f_{n+1}\\&=f_{m-1}\times f_n+f_m\times f_{n+1}\end{aligned}$$ 成立。 - 当 $m\in[1,k],n=k+1$ 时（其实本质相同，但是为了完整还是写了）： $$\begin{aligned}f_{m+n}&=f_{m+n-2}+f_{m+n-1}\\&=f_{m-1+n-1}+f_{m+n-1}\\&=f_{m-2}\times f_{n-1}+f_{m-1}\times f_n+f_{m-1}\times f_{n-1}+f_{m}\times f_{n}\\&=f_{m-2}\times f_{n-1}+f_{m-1}\times f_{n-1}+f_{m-1}\times f_n+f_{m}\times f_{n}\\&=f_m\times f_{n-1}+f_{m+1}\times f_n\\&=f_{m-1}\times f_n+f_m\times f_{n+1}\end{aligned}$$ 成立。 - 当 $m=n=k+1$ 时： $$\begin{aligned}f_{m+n}&=f_{m+n-2}+f_{m+n-1}\\&=f_{m+n-2}+f_{m+n-3}+f_{m+n-2}\\&=f_{m-1+n-1}+f_{m-1+n-2}+f_{m-1+n-1}\\&=f_{m-2}\times f_{n-1}+f_{m-1}\times f_n+f_{m-2}\times f_{n-2}+f_{m-1} \times f_{n-1}+ f_{m-2}\times f_{n-1}+f_{m-1}\times f_n\\&=f_{m-1}\times f_n+f_{m-2}\times(f_{n-1}+f_{n-2}+f_{n-1})+f_{m-1}\times(f_n+f_{n-1})\\&=f_{m-1}\times f_n+f_{m-2}\times f_{n+1}+f_{m-1}\times f_{n+1}\\&=f_{m-1}\times f_n+f_m\times f_{n+1}\end{aligned}$$ 成立。 因此当 $m,n\in[0,\infty)$ 时成立。 接下来考虑负数的情况： 假设 $m,n\in[k,\infty)$ 时成立，则当 $m,n\in[k-1,\infty)$ 时，同样新增三种情况： - 当 $m=k-1,n\in[k,\infty)$ 时： $$\begin{aligned}f_{m+n}&=f_{m+n+2}-f_{m+n+1}\\&=f_{m+1+n+1}-f_{m+1+n}\\&=f_m\times f_{n+1}+f_{m+1}\times f_{n+2}-f_{m}\times f_{n}-f_{m+1}\times f_{n+1}\\&=f_m\times(f_{n+1}-f_n)+f_{m+1}\times(f_{n+2}-f_{n+1})\\&=f_{m}\times f_{n-1}+f_{m+1}\times f_n\\&=f_{m-1}\times f_n+f_m\times f_{n+1}\end{aligned}$$ 成立。 - 当 $m\in[k,\infty),n=k-1$ 时： $$\begin{aligned}f_{m+n}&=f_{m+n+2}-f_{m+n+1}\\&=f_{m+1+n+1}-f_{m+n+1}\\&=f_{m}\times f_{n+1}+f_{m+1}\times f_{n+2}-f_{m-1}\times f_{n+1}-f_m\times f_{n+2}\\&=f_{n+1}\times(f_m-f_{m-1})+f_{n+2}\times (f_{m+1}-f_m)\\&=f_{m-2}\times f_{n+1}+f_{m-1}\times f_{n+2}\\&=f_{m-2}\times f_{n+1}+f_{m-1}\times (f_n+f_{n+1})\\&=f_{m-2}\times f_{n+1}+f_{m-1}\times f_n + f_{m-1}\times f_{n+1}\\&=f_{m-1}\times f_n+(f_{m-2}+f_{m-1})\times f_{n+1}\\&=f_{m-1}\times f_n+f_m\times f_{n+1}\end{aligned}$$ 成立。 - 当 $m=n=k-1$ 时： $$\begin{aligned}f_{m+n}&=f_{m+n+2}-f_{m+n+1}\\&=f_{m+n+2}-(f_{m+n+3}-f_{m+n+2})\\&=f_{m+n+2}-f_{m+n+3}+f_{m+n+2}\\&=f_{m+1+n+1}-f_{m+2+n+1}+f_{m+1+n+1}\\&=f_{m}\times f_{n+1}+f_{m+1}\times f_{n+2} - f_{m+1}\times f_{n+1}-f_{m+2}\times f_{n+2} +f_{m}\times f_{n+1}+f_{m+1}\times f_{n+2}\\&=f_m\times f_{n+1}+f_{m}\times f_{n+1}+f_{m+1}\times (f_{n+2}-f_{n+1})-(f_{m+2}-f_{m+1})\times f_{n+2}\\&=f_{m}\times f_{n+1}+f_{m}\times f_{n+1}+f_{m+1}\times f_n-f_m\times f_{n+2}\\&=f_{m}\times f_{n+1}-f_m\times(f_{n+2}-f_{n+1}) +f_{m+1}\times f_n\\&=f_m\times f_{n+1}-f_m\times f_n+f_{m+1}\times f_n\\&=(f_{m+1}-f_m)\times f_n+f_m\times f_{n+1}\\&=f_{m-1}\times f_n+f_m\times f_{n+1}\end{aligned}$$ 成立。 因此当 $m,n\in(-\infty,\infty)$ 时成立，证毕。 有了这两个结论以后，就可以开始做这道题了。 求斐波那契数列想到矩阵快速幂。路径查询问题先想树剖。将以 $x$ 为根子树内的点 $u$ 权值加上 $f_{d_u-d_x+k}$，相当于加上 $f_{d_{u}-1}\times f_{k-d_x}+f_{d_u}\times f_{k-d_x+1}$。将 $f_{d_{u}-1}$ 和 $f_{d_u}$ 分开维护（分别记为 $a,b$），发现系数是常数，可做。对树剖后的序列建线段树，修改操作就是将子树在序列上对应的区间的两个系数区间加，维护区间权值和 $sum$，$a$ 值的和 $v_a$，$b$ 值的和 $v_b$，$a$ 值的系数懒标记 $tg_a$，$b$ 值的系数懒标记 $tg_b$。 记 $ls$ 为左子，$rs$ 为右子，$x$ 为当前节点（和输入的不同）。下传就是： ```cpp void down(int x){ if(tga[x]){//需要下传。 sum[ls]=(sum[ls]+va[ls]*tga[x]%M)%M;//答案加上 va[ls]*tga[x]，注意这里要拿 a 值的和来乘，因为 tga[x] 是当前区间的系数，区间内每一项都要乘上这么多，根据乘法分配律就是给和乘上这么多。下面同理。 tga[ls]=(tga[ls]+tga[x])%M; sum[rs]=(sum[rs]+va[rs]*tga[x]%M)%M; tga[rs]=(tga[rs]+tga[x])%M; tga[x]=0; } if(tgb[x]){ sum[ls]=(sum[ls]+vb[ls]*tgb[x]%M)%M; tgb[ls]=(tgb[ls]+tgb[x])%M; sum[rs]=(sum[rs]+vb[rs]*tgb[x]%M)%M; tgb[rs]=(tgb[rs]+tgb[x])%M; tgb[x]=0; } } ``` 查询就是跳链查询。 时间复杂度为 $\mathcal{O}(M\log^2N)$，空间复杂度为 $\mathcal{O}(N)$。 **[评测记录](https://www.luogu.com.cn/record/109076181 "评测记录") [代码](https://www.luogu.com.cn/paste/rigw2gi6)** # 离线技巧 **[洛谷 P4312 [COI2009] OTOCI](https://www.luogu.com.cn/problem/P4312)** / **[SP4155 OTOCI - OTOCI](https://www.luogu.com.cn/problem/SP4155)** > - 给出一个 $n$ 个点的图，一开始所有点都是孤点，点 $i$ 有权值 $w_i$。有三种操作，共 $q$ 次： > > - $\texttt{bridge }u\texttt{ }v$，查询点 $u,v$ 是否连通，若不连通，则在两点之间连边。 > > - $\texttt{penguins }u\texttt{ }x$，将 $w_u\leftarrow x$。 > > - $\texttt{excursion }u\texttt{ }v$，查询点 $u,v$ 路径上的点权和，若不连通，输出 $\texttt{impossible}$。 > > - $n\le 3\times 10^4$，$q\le 3\times 10^5$。 由于每次在不连通的点之间连边，因此最终图的形态肯定是一个**森林**，且每次询问的路径，若两点连通，他们的路径**一定在森林上**。因此考虑处理出 $\texttt{impossible}$ 的答案，然后先建出森林并树链剖分，将询问离线，用树状数组维护信息并差分计算答案。 时间复杂度为 $\mathcal{O}(q\log^2 n)$，空间复杂度为 $\mathcal{O}(n+q)$，可以接受。 **[评测记录](https://www.luogu.com.cn/record/108625319) [代码](https://www.luogu.com.cn/paste/8qkayqtm)** **习题** **Ⅰ - [洛谷 P2542 航线规划](https://www.luogu.com.cn/problem/P2542)** > - 给出一个 $n$ 个点 $m$ 条边的无向图，支持两种操作： > > - $\texttt{1 }u \texttt{ }v$，询问 $u,v$ 两点间的割边数。 > > - $\texttt{0 }u\texttt{ }v$，断掉 $u,v$ 之间的边。 > > - 记操作总数为 $q$，$n\le 3\times 10^4$，$m\le 10^5$，$q\le 4\times 10^4$。 删边不好维护，考虑离线倒序操作，变成加边操作和查询操作。回忆一下静态的两点间割边数怎么做，先建出边双树，然后答案就是两点边双连通分量之间的树上距离。故先离线建出边双树，树上边权置 $1$，并树剖、边转点。然后每加一条边，相当与两点边双间的割边全部失效，区间推平成 $0$，然后查询就是两点边双路径上的边权和。 来理解一些细节： - 每次加边后，边双树的形态应当发生改边，但是两点树上路径可能包含失效的割边。其实是没有影响的，两点间存在失效的割边相当于已经存在了 $0$ 边，再次推平成 $0$ 并不影响，并且也可以把真正的割边置 $0$。 - 查询会受到非割边的影响吗？其实是不会的，考虑那些 $0$ 边，应当将这些边构成的极长链全部缩成一个点，然后统计剩下 $1$ 边的贡献。但是在树上查询的时候，$1$ 边的贡献已经存在，非割边权为 $0$ 对答案没有贡献。故这样做是对的。 时间复杂度为 $\mathcal{O}(q \log^2 n)$，空间复杂度为 $\mathcal{O}(n+m+q)$。 **[评测记录](https://www.luogu.com.cn/record/107968177) [代码](https://www.luogu.com.cn/paste/rqpa7e46)**