树链剖分&线段树模板 / p3384

前言

树剖是连接图论和数据结构的一道桥梁，绝大多数数据结构都是建立在线性表中，

与二维的图天然隔绝，而树剖则提供了一个很好的转换方法

可以将二维的图转化为一维的表，以重链选择较多，长链也有

利用dfn序将树存储与线段树中，这个性质很重要：dfn序连续的节点在树链中也连续

树剖的代码相对好理解一些，不过代码比较长，其大致实现思路是：

1. 进行第一次dfs遍历，求出以下数组：pre[], deep[], num[], son[]， 即父节点、深度数组、子树大小和重子节点，此次dfs为无差别搜索
2. 然后进行第二次dfs遍历，记录以下数组：dfn[], top[], rk[]，即dfn序，链首节点和链内排名，此次dfs为优先重子搜索

至此，便可以利用dfn序和线段树结合吗，共同维护此树

一、 例题 p3384

题目链接 洛谷 p3384

二、 思路及代码 1. 思路

很经典的一道树剖与线段树的结合，套板子即可

2. 代码

代码如下 ：

#include 
#include 
// #define int long long 会RE ？？？
using namespace std;
const int maxn = 2e5 + 5;
int mod;
int n, m, r;
int pre[maxn], deep[maxn], num[maxn], son[maxn];  // 第一次dfs的变量
int dfn[maxn], top[maxn], rk[maxn], id;  // 第二次dfs的时候用到的变量
int val[maxn], dfnval[maxn];             // 建树时用dfn序下的val
struct e {
  int to, next;
} edge[maxn