dfs序和树链剖分两者都借助hash的思想是将树形转化成线性的算法，前者主要处理子树问题，后者主要处理链的问题。
1.dfs序
定义： 顾名思义是按照dfs的顺序标号。
重要性质：每棵子树内的标号都是连续的，某些链的标号也是连续的。
代码：
int timetmp;///时间戳，计数器 int in[maxn];///表示dfs进某节点的时间 int out[maxn];///表示dfs出某节点的时间 ///差值就是子树的节点个数 vector<int>e[maxn];///存图 void dfs(int u,int fa){ in[u]=++timetmp; for(int i=0;i<e[u].size();i++){ int j=e[u][i]; if(j==fa) continue; dfs(j,u); } out[u]=timetmp; }
例题1：（卿学姐给的例题 没找到来源）
题意：两种操作 1.将子树的所有节点的权值都+v 2.查询某子树的权值的max
思路：按照dfs序给所有节点标号，这样就将树上问题转化成了区间问题，由重要性质我们可以把操作一转化为区间加法，操作二转化为区间最值，用线段树维护就可以了。
例题2：（POJ3321）
题意：两种操作 1.修改某个节点的权值，如果原来是1，修改为0，如果原来是0，修改为1 ； 2.查询某子树的权值和
思路：转化为dfs序后，就转化成了单点修改、区间查询的问题，用树状数组或线段树维护即可。
2.树链剖分（重链剖分 logn）
基本概念：（sz[x]表示x的子树个数）
重儿子：某节点的所有子节点里sz[x]最大的子节点(如果有多个就随便取一个)
轻儿子：一个节点除了重儿子以外的儿子
重链：从一个轻儿子（根节点也是轻儿子）开始，每次往重儿子走连出的链
轻链：除了重链全是轻链
模拟过程：
第一遍dfs:记录节点的父亲、重儿子、深度、大小
第二遍dfs:记录节点权值的dfs序和时间戳，当前节点所在重链的头是谁
int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn]; ///son[]重儿子编号,id[]新编号,fa[]父亲节点,cnt dfs_clock/dfs序,dep[]深度,siz[]子树大小,top[]当前链顶端节点 int res=0; ///查询答案 inline void dfs1(int x,int f,int deep){//x当前节点，f父亲，deep深度 dep[x]=deep;//标记每个点的深度 fa[x]=f;//标记每个点的父亲 siz[x]=1;//标记每个非叶子节点的子树大小 int maxson=-1;//记录重儿子的儿子数 for(int i=h[x];i;i=ne[i]){ int y=e[i]; if(y==f)continue;//若为父亲则continue dfs1(y,x,deep+1);//dfs其儿子 siz[x]+=siz[y];//把它的儿子数加到它身上 if(siz[y]>maxson)son[x]=y,maxson=siz[y];//标记每个非叶子节点的重儿子编号 } } inline void dfs2(int x,int topf){//x当前节点，topf当前链的最顶端的节点 id[x]=++cnt;//标记每个点的新编号 wt[cnt]=w[x];//把每个点的初始值赋到新编号上来 top[x]=topf;//这个点所在链的顶端 if(!son[x])return;//如果没有儿子则返回 dfs2(son[x],topf);//按先处理重儿子，再处理轻儿子的顺序递归处理 for(int i=h[x];i;i=ne[i]){ int y=e[i]; if(y==fa[x]||y==son[x])continue; dfs2(y,y);//对于每一个轻儿子都有一条从它自己开始的链 } }
重要性质：
重链上的编号都是连续的。
任何一条路径都是由重链的一部分和叶子节点组成的。
除根节点外的任意一个节点的父节点一定在一条重链上。
然后一般就再用树状数组或线段树维护信息。
例题：（洛谷P3384）
思路：
树剖之后操作3和操作4都利用区间修改和区间查询可以解决。
inline int qSon(int x){///操作4 res=0; query(1,1,n,id[x],id[x]+siz[x]-1);//子树区间右端点为id[x]+siz[x]-1 return res; } inline void updSon(int x,int k){//操作3 update(1,1,n,id[x],id[x]+siz[x]-1,k); }
对于操作1和操作2，如果两个节点在一条重链上，问题就转化成了区间修改和区间查询；如果不在一条重链上，可以维护两个指针指向两个节点，不停地让dep[top[i]]大的节点的指针沿着所在重量往上跳，同时在线段树上进行操作，直到两指针到同一节点或同一重链。
int qRange(int x,int y){//操作2 表示求树从 x到 y 结点最短路径上所有节点的值之和 int ans=0; while(top[x]!=top[y]){//当两个点不在同一条链上 if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点 res=0; query(1,1,n,id[top[x]],id[x]);//ans加上x点到x所在链顶端 这一段区间的点权和 ans+=res; ans%=mod;//按题意取模 x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点 } //直到两个点处于一条链上 if(dep[x]>dep[y])swap(x,y);//把x点变为深度更深的那个点 res=0; query(1,1,n,id[x],id[y]);//这时再加上此时两个点的区间和即可 ans+=res; return ans%mod; }
待补
【牛客】2020牛客暑期多校训练营（第七场）C- A National Pandemic
