树形结构转线形结构——树链剖分——子树问题

昨天遇到了这样一道题目：

一个公司有 n 个员工，编号从 0 到 n-1 ，每个员工都有一个直系上司，编号为 0 的是整个公司的董事长（包工头），现在，给出每个员工每月的初始工资，为了鼓励最佳员工和最佳部门，现在，董事会会有以下两种询问：

1、employee x y z ：询问员工 x 的工资，如果员工的 x 的工资小于 y ，那么就给他（她）涨 z 元

2、department x y z ：询问员工 x 领导的部门的平均工资，如果平均工资小于 y ，那么就给这个部门的每个员工涨 z 元

当时一看到题目就知道是树链剖分，对于树链剖分我只知道个大概，队友给我讲了他的做法，但是没有听明白，最后还是没有在比赛期间做出来，感觉甚是可惜，深感以后决不能再因为这样挂题，于是昨天晚上还有今天一直在恶补树链剖分，只是搞懂了一些简单的问题，现在总结一下。

这样的题目，只是涉及到节点和子树的问题，并不涉及到对树上的路径进行操作，显得要简单一点。

为了深刻的理解树链剖分，我们的首先来看一下树的遍历，这里指的是DFS

在遍历的时候，假定我们给每一个遍历的节点一个从小到大的编号，这样的编号有什么特点呢？我们来看一下：

现在假定我们有上面一颗树：整棵树的根是 1 ，我们从根节点遍历，遍历的方式利用 先根遍历 ，1 节点的编号是 1 ，然后遍历的时候遇到一个新的节点，序号就 +1，这样，我们不难得到以下的序号：

节点 ：1 2 4 5 8 9 6 3 7

节点序号：1 2 3 4 5 6 7 8 9

得到这个表格有什么用呢？

我们仔细观察一下：

节点 1 是整棵树的根，节点 1 的序号是整棵树的节点里面序号最小的，并且，以节点 1 的为根的数的节点的序号全部是紧接着着节点 1 的序号的

节点 2 是子树（2 4 5 6 8 9）的根，节点 2 的序号是以节点 2 为根的树中节点序号最小的，并且，以节点 2 为根的子树的节点的序号全部是紧接着节点 2 的

节点 5 是子树（5 8 9）的根，节点 5 的序号是以节点 5 为根的树中节点序号最小的，并且，以节点 5 为根的子树的节点的序号全部是紧接着节点 5 的

。。。。。。

我们发现了这样的一条规律，以节点 u 为根的子树 T，T 中所有的节点的序号一定是大于节点 u 的序号的，并且，我们得到的 DFS序列中，T 中所有的节点一定是紧接着 U 出现的

当然，这只是一个小小的规律，直觉强的觉得不用证明，肯定是这样的，但既然提出了这个规律，我还是简单的证明一下这个规律是正确的吧

1、证明 T 中所有节点的序号大于 U

我们在遍历 T 中所有节点的时候，遍历的方式是先根后子树，那么，那么我们一定是先遍历的节点 U ，然后再遍历以节点 U 为根的子树 T 中的所有节点，这样，节点 U 的序号一定是子树中所有节点的序号中最小的

2、证明 T 中的所有节点在生成的DFS序列中一定是紧接着节点 U 的出现的

证明这个问题，其实就跟上面的问题一样，同样因为我们是先根遍历的，那么作为根节点的 U 在DFS序列中一定是出现在 T 中所有节点的最前面，而中途不可能遍历到其他子树的节点，如果遍历到了，说明以 U 为根的子树已经遍历完了

得到了这样的性质，我们就可以把对整棵子树的操作改成对生成的 DFS 序列中的节点进行操作了，这就变成了简单的 线段树成段更新，成段查询问题了，而这道题我们只需要加一个预处理——得到 DFS 序列，同时得到 DFS 序列中，以某一节点为根的子树在DFS序列中的结束位置即可，我们可以用 low [u] 来记录生成的 DFS序列 中，以 U 节点为根的子树到哪里截止，不难想出如下地推方程：low[u] = max( low[u_son1] , low[u_son2] , ... low[u_sonk] )

下面给出 DFS 预处理过程：

之所以 low[v] = ind 是根据 DFS过程的性质，小小的利用一下而已。

这道题不知道队友是怎么做的，不过思路是一样的，但是昨天一直挂在按照原来的序号输出所有员工的工资上了，我加了个 id[u] 表示节点 u 在生成的 DFS 序列中的起始位置，这样就解决了按照原来序号输出的问题了

这里是原题连接：有兴趣的朋友可以去切一切，虽然题目很水。。 Money out of Thin Air

有什么细节还不明白的可以看看我的代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>#include <string>#include <queue>#include <stack>#include <map>#include <set>#include <list>#define INT_INF 0x3fffffff#define LL_INF 0x3fffffffffffffff#define EPS 1e-12#define MOD 1000000007#define PI 3.141592653579798#define N 100005using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef double DB;struct data{    int en,next;} edge[N*2];int tot,head[N];int sum[2*N];int id[N] , low[N] , ind;void add_edge(int st,int en){    edge[tot].en=en;    edge[tot].next=head[st];    head[st]=tot++;}void dfs(int v,int pre,int dep){    id[v]=++ind;    for(int i=head[v];i!=-1;i=edge[i].next)    {        if(edge[i].en==pre) continue;        dfs(edge[i].en,v,dep+1);    }    low[v]=ind;}void update(int *a,int pos,int val){    while(pos<2*N)    {        a[pos]+=val;        pos+=pos&(-pos);    }}int get(int *a,int pos){    int tmp=0;    while(pos>0)    {        tmp+=a[pos];        pos-=pos&(-pos);    }    return tmp;}int main(){    int n,a,b;    memset(head,-1,sizeof(head));    tot=0;    scanf("%d",&n);    for(int i=1;i<n;i++)    {        scanf("%d%d",&a,&b);        add_edge(a,b);        add_edge(b,a);    }    memset(id,0,sizeof(id));    memset(low,0,sizeof(low));    ind=0;    dfs(1,-1,0);    memset(sum,0,sizeof(sum));    for(int i=1;i<=n;i++)        update(sum,id[i],1);    char s[2]; int pos , m;    scanf("%d",&m);    for(int i=1;i<=m;i++)    {        scanf("%s%d",s,&pos);        if(s[0]=='Q') printf("%d\n",get(sum,low[pos])-get(sum,id[pos]-1));        else        {            int val=get(sum,id[pos])-get(sum,id[pos]-1);            if(val==1)                update(sum,id[pos],-1);            else                update(sum,id[pos],1);        }    }    return 0;}