说在前面的

和欧拉序都是非常有力的工具，我们应该熟练的运用两者。而且 序也不必局限于树上的 序，其实一般图也有 序，有兴趣的朋友可以参考 算法。

  • 以下的 序，全部指树上的 序， 序即使在树上，仍然不是唯一的。
  • 以下的 ，全部指以 为根，子树的大小。

dfs 序

引入

如何判断 是否有所属关系，也就是 ，多次询问。我们发现我们并不能把每个节点的 记录下来，这使我们不太好查询是否 。

  • 我们可以考虑模拟 的过程，先遍历所有儿子，然后才去遍历其他子树。那么我们发现，如果按照遍历顺序，在第一次遍历到这个节点时，将该节点压入数组。那么节点在新数组的位置叫做这个节点的 序。由此我们得到了一棵树的 序序列，但是序列又有什么性质呢？

性质

的性质是非常多，而且非常重要的。这里选取一些常用的进行讲解。

  • 一个子树的 序一定是连续的，而且节点 的子树大小也就是 序中，从 开始，到后面连续的 个元素结束，这些元素全是属于 的子树的。这个可以通过分析 的过程得到，因为我们要遍历完一个子树才会回溯，所以在没有遍历完 个元素时，是不会退出的。

图片说明

  • 序列是由连续的链构成的，而且每一条链上的节点深度由浅到深依次排列。这个也可以通过分析 的过程得到。

欧拉序(括号序列)

这个欧拉序和 序其实有非常多的共同点，在构造时的唯一区别是， 是在只第一次访问时加入数组中。而欧拉序还要在回溯时，把该节点压入数组。如果我们把第一次访问，当作是加入左括号 ，回溯看作是加入右括号 。那么最后 遍历完整个树，最后得到的就是一个括号序列。

性质

由于欧拉序维护了出栈的标记，所以相比 序，更加强大，维护的东西也更加多。

  • 每个节点会出现两次。因为入栈出栈都维护了。

  • 相邻两个节点的深度相差 。 的访问是连续的，回溯也是连续的，这个还是比较显然的。

  • 可以维护树上路径。这个就比较有意思了。我们把第一次进入数组的位置命名为 ，第二次称之为 。那么 是要分类讨论的。

    • 。那么 从 到 中只出现了一次的元素。为什么是只出现一次呢，由于 所以出现两次的，是其它子树的元素，与 无关。
    • 。那么 是从 到 中只出现一次的元素，和 组成的。出现两次的元素一定是 的其它子树中的元素，而 先于 遍历，而 还没遍历完，所以 还没有进入数组，所以要把 单独加入路径中。这个也是树上莫队算法的一个依据。

图片说明

  • 维护祖先儿子关系。同 序的维护。而且我们还发现这个节点的左括号到右括号中的所有元素都是子树元素，而且左右括号可以完美匹配 。

例题

出于写博客服务于大家和自己，这里先将一点关于 序的基础题，最后再讲讲牛客的例题（谢谢理解）。

Tree Queries

题意

给你一个以 为根的有根树，每回询问 个节点 。求出是否有一条以根节点为一端的链，使得询问的每个节点到此链的距离均 。只需输出可行性, 无需输出方案。

分析

无论是哪种方案，想要使链到节点的距离 。那么只有三种可能。

  • 经过父亲。
  • 经过自己。
  • 经过一个直接的儿子。

但是我们发现这三种其实都必须经过父亲。所以把 的父亲的 序由小到大排序，最后判断后一个是不是当前节点的儿子，就可以了，这个可以通过 序做到。复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch=getchar();}
    return f?-x:x;
}
const int N = 2e5+100;
int n,m,dep[N],fa[N],dfn[N],Id,st[N],si[N];
vector<int> G[N];
bool cmp(int x,int y) {return dep[x] < dep[y];}
void dfs(int x,int f,int de) {
    dep[x] = de;dfn[x] = ++Id;si[x]=1;fa[x] = f;
    for(auto y:G[x]) {if(y == f) continue;dfs(y,x,de+1);si[x]+=si[y];}    
}
int main()
{
    n = read();m = read();
    for(int i = 1;i < n;i++) {
        int x = read(),y = read();
        G[x].push_back(y);G[y].push_back(x);
    }
    dfs(1,1,1);
    while(m--) {
        int sum = read(),check = 0;
        for(int i = 1;i <= sum;i++) st[i] = fa[read()];
        sort(st+1,st+1+sum,cmp);
        for(int i = 2;i <= sum;i++) {
            if(dfn[st[i]] >= dfn[st[i-1]] && dfn[st[i]] <= dfn[st[i-1]] + si[st[i-1]] - 1) continue;
            check = 1;
        }
        !check?puts("Yes"):puts("No");
    }
}

Military Problem

分析

这个就是模拟 的过程就行了，判断可以直接输出 序对应的元素。输出前判断一下 于 的关系就好了。小细节，如果要用链式前向星存边，那么根据遍历顺序，应该倒着建边，这个稍微分析一下就好了。最后总复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1000;
int ecnt,si[N],id[N],pos[N],head[N],n,Id,to[N];
struct Edge {int to,nxt;}e[N];
int read() {int x;scanf("%d",&x);return x;}
void add(int x,int y) {e[++ecnt].to = y;e[ecnt].nxt = head[x];head[x] = ecnt;}
void dfs(int x) {
    pos[id[x] = ++Id] = x;si[x] = 1;
    for(int i = head[x];i;i=e[i].nxt) dfs(e[i].to),si[x] += si[e[i].to];
}
int main() {
    n = read();int Q = read();
    for(int i = 2,fa;i <= n;i++) to[i] = read();
    for(int i = n;i > 1;i--) add(to[i],i); 
    dfs(1);
    while(Q--) {
        int rt = read(),k = read();
        if(si[rt] < k) puts("-1");
        else printf("%d\n",pos[id[rt] + k - 1]);
    }
}

选点

分析

不太一样的 序，但是核心思想没有区别。由于我们选出来的点要满足 。那么我们可以先遍历 这样的顺序遍历，这样把树映射到序列上，这样问题就形式化了。求问一个序列的最长上升子序列。这样就可以随便做了，可以用数据结构优化一下，总复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1000;
int read() {int x;scanf("%d",&x);return x;}
int n,lc[N],rc[N],id[N],Id,pos[N],f[N],ans,w[N],t[N];
void dfs(int x) {
    pos[id[x] = ++Id] = x;
    if(rc[x]) dfs(rc[x]);if(lc[x]) dfs(lc[x]);
}
void upd(int x,int v) {for(int i = x;i <= n;i += i & -i) t[i] = max(t[i],v);}
int ask(int x) {int tot = 0;for(int i = x;i;i -= i & -i) tot = max(tot,t[i]);return tot;}
int res[N];
int main() {
    n = read();
    for(int i = 1;i <= n;i++) res[i] = w[i] = read();
    for(int i = 1;i <= n;i++) lc[i] = read(),rc[i] = read();
    sort(res + 1,res + 1 + n);
    int cnt = unique(res + 1,res + 1 + n) - res - 1;
    for(int i = 1;i <= n;i++) w[i] = lower_bound(res + 1,res + cnt + 1,w[i]) - res;
    dfs(1);
    for(int i = 1;i <= n;i++) {
        f[i] = ask(w[pos[i]] - 1) + 1;
        ans = max(f[i],ans);
        upd(w[pos[i]],f[i]);
    }
    printf("%d\n",ans);
    return 0;
}

Tree Requests

题意

给定一个以 为根的 个节点的树，每个点上有一个字母 到 ，每次询问 ，查询以 为根的子树内深度为 的节点上的字母重新排列之后是否能构成回文串。

分析

关于这题，我并没有非常好的基于 序的做法，抱歉。这里提供一种树上启发式合并的做法。构成回文串的字母应该满足 。 表示 这个字符出现的次数。那么根据每个元素只会在跳轻边时合并，而任何一个节点到根路径上只有 条轻边，那么总复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int M = 5e5+1000;
struct Query{
    int de,id;
};
int n,m;
vector<int> G[M];
vector<Query> Q[M];
int L[M],R[M],id[M],T;
int dep[M],son[M],si[M];
int check[M],ans[M];
char A[M];
void dfs(int u,int d) {
    L[u] = ++T;dep[u] = d;
    id[T] = u;son[u] = 0;si[u] = 1;
    for(int i = 0;i < G[u].size();i++) {
        int v = G[u][i];
        dfs(v,d+1);
        if(si[v]>si[son[u]]) son[u] = v;
        si[u] += si[v];
    }
    R[u] = T;
}
void add_point(int x) {
    int r = A[x] - 'a',d = dep[x];
    check[d] ^= (1<<r);
}
void add_tree(int x) {
    for(int i = L[x];i <= R[x];i++) add_point(id[i]);
}
void solve(int x) {
    for(int i = 0;i < G[x].size();i++) {
        int y = G[x][i];
        if(y == son[x]) continue;
        solve(y);add_tree(y);
    }
    if(son[x]) solve(son[x]);
    for(int i = 0;i < G[x].size();i++) {
        int y = G[x][i];
        if(y == son[x]) continue;
        add_tree(y);
    }
    add_point(x);
    for(int i = 0;i < Q[x].size();i++) {
        int d = Q[x][i].de,r = check[d],id = Q[x][i].id;
        ans[id] = (r==(r&-r));
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i = 2,f;i <= n;i++) {
        scanf("%d",&f);
        G[f].push_back(i);
    }
    dfs(1,1);
    scanf("%s",A+1);
    for(int i = 1;i <= m;i++) {
        int x,d;
        scanf("%d%d",&x,&d);
        Q[x].push_back((Query){d,i});
    }
    solve(1);
    for(int i = 1;i <= m;i++) {
        if(ans[i]) puts("Yes");
        else puts("No");
    }
    return 0;
}

Colorful Tree

题意

支持两个操作。改变一个节点的颜色。查询由一种颜色构成的最小生成树的价值。

分析

我们对于一个树上选一些节点使他们的联通的代价最小。这个问题，我们可以按 序由大到小排序，这样依次联接是没有重复路径的。这个可以手摸一下，也可以通过 的性质得到。那么我们现在要处理的就是，如果删除和添加一个节点。我们考虑到，删除一个节点，那么这个节点左右两个元素的 序仍然是连续的，所有我们可以考虑一个元素的贡献，为 。那么我们就开个平衡树维护一下这个颜色的所有元素，动态的维护答案就好了。总的复杂度为 。

  • 小技巧，树上的节点 的简单路径只有一条，其长度为 。

    代码

#include<bits/stdc++.h>
using namespace std;
#define It set<int>::iterator
const int N = 1e5 + 1000;
int read() {int x;scanf("%d",&x);return x;}
struct Edge {int to,nxt;}e[N<<1];
int id[N],rid[N],col[N],Id,head[N],fa[N][21],dep[N],n,ecnt;
void add(int x,int y) {e[++ecnt] = (Edge){y,head[x]};head[x] = ecnt;}
int lca(int idx,int idy) {
    int x = rid[idx],y = rid[idy];
    if(dep[x] < dep[y]) swap(x,y);
    int k = dep[x] - dep[y];
    for(int i = 20;~i;i--) if((k >> i) & 1) x = fa[x][i];
    if(x == y) return x;
    for(int i = 20;~i;i--) if(fa[x][i] ^ fa[y][i]) x = fa[x][i],y = fa[y][i];
    return fa[x][0];
}
int dis(int idx,int idy) {
    int x = rid[idx],y = rid[idy];
    return (dep[x] + dep[y] - 2 * dep[lca(idx,idy)]);
}
void dfs(int x,int f) {
    fa[x][0] = f;rid[id[x] = ++Id] = x;
    for(int i = 1;i <= 20;i++) fa[x][i] = fa[fa[x][i-1]][i-1];
    for(int i = head[x];i;i=e[i].nxt) {
        int y = e[i].to;if(y == f) continue;
        dep[y] = dep[x] + 1;dfs(y,x);
    }
}
struct MST {
    set<int> s;int sum;
    void add(int x) {
        s.insert(x);It it = s.find(x);
        int L = 0,R = 0;
        ++it;if(it != s.end()) R = *it;
        --it;if(it != s.begin()) --it ,L = *it;
        if(L && R) sum -= dis(L,R);
        if(L) sum += dis(L,x);if(R) sum += dis(x,R);
    }
    void del(int x) {
        It it = s.find(x);
        int L = 0,R = 0;
        ++it;if(it != s.end()) R = *it;
        --it;if(it != s.begin()) --it ,L = *it;
        if(L && R) sum += dis(L,R);
        if(L) sum -= dis(L,x);if(R) sum -= dis(x,R);
        it = s.find(x);s.erase(it);
    }
    int ans() {return (sum + dis(*s.begin(),*s.rbegin())) / 2;}
}A[N];

int main() {
    n = read();
    for(int i = 1,x,y;i < n;i++) {
        x = read();y = read();
        add(x,y);add(y,x);
    }    
    dfs(1,0);
    for(int i = 1;i <= n;i++) {
        col[i] = read();A[col[i]].add(id[i]);
    }
    int Q = read();
    while(Q--) {
        char ch[10];scanf("%s",ch + 1);
        if(ch[1] == 'U') {
            int x = read(),y = read();
            A[col[x]].del(id[x]);
            col[x] = y;
            A[col[x]].add(id[x]);
        }
        else {
            int x = read();
            if(A[x].s.empty()) puts("-1");
            else printf("%d\n",A[x].ans());
        }
    }
}

求和 & Propagating tree

由于这两道题，没有什么本质上的区别。这里就把思路呈现出来。

分析

要求维护两个操作，查询单点和修改子树。我们可以直接用线段树在 序乱搞，也可以转化为差分之后用树状数组维护。而 这道题，我们用奇偶分个组，也就做完了。

  • 这里有个小技巧，一般对于链上查询，都可以差分成子树修改。虽然这里没有用到，但是我认为这个还是非常重要的。因为维护 序，比链上操作要简单的多。

    代码

    #include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1000;
int ecnt,L[N],R[N],head[N],n,rt,Id;
struct Edge {int to,nxt;}e[N << 1];
int read() {int x;scanf("%d",&x);return x;}
void add(int x,int y) {e[++ecnt].to = y;e[ecnt].nxt = head[x];head[x] = ecnt;}
void dfs(int x,int f) {
  L[x] = ++Id;
  for(int i = head[x];i;i=e[i].nxt) if(e[i].to ^ f) dfs(e[i].to,x);
  R[x] = Id;
}
int val[N],t[N << 2];
void update(int u,int l,int r,int pos,int k) {
  if(l == r) {t[u] += k;return;}
  int mid = l + r >> 1;
  if(pos <= mid) update(u << 1,l,mid,pos,k);
  else update(u << 1 | 1,mid + 1,r,pos,k);
  t[u] = t[u << 1] + t[u << 1 | 1];
}
int ask(int u,int l,int r,int L,int R) {
  if(l > R || r < L) return 0;
  if(L <= l && r <= R) return t[u];
  int mid = l + r >> 1;
  return (ask(u << 1,l,mid,L,R) + ask(u << 1 | 1,mid + 1,r,L,R));
}
int main() {
  n = read();int Q = read();rt = read();
  for(int i = 1;i <= n;i++) val[i] = read();
  for(int i = 1,a,b;i < n;i++) {
      a = read();b = read();
      add(a,b);add(b,a);
  }
  dfs(rt,0);
  for(int i = 1;i <= n;i++) update(1,1,n,L[i],val[i]);
  while(Q--) {
      int opt = read();
      if(opt == 2) {
          int x = read();
          printf("%d\n",ask(1,1,n,L[x],R[x]));
      }
      else {
          int x = read(),y = read();
          update(1,1,n,L[x],y);
      }
  }
}
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1000;
int ecnt,L[N],R[N],head[N],n,Id;
bool col[N];
struct Edge {int to,nxt;}e[N << 1];
int read() {int x;scanf("%d",&x);return x;}
void add(int x,int y) {e[++ecnt].to = y;e[ecnt].nxt = head[x];head[x] = ecnt;}
void dfs(int x,int f,int c) {
  L[x] = ++Id;col[x] = c;
  for(int i = head[x];i;i=e[i].nxt) if(e[i].to ^ f) dfs(e[i].to,x,1 - c);
  R[x] = Id;
}
int val[N];
struct SegmentTree {
  int t[N << 2];
  void update(int u,int l,int r,int pos,int k) {
      if(l == r) {t[u] += k;return;}
      int mid = l + r >> 1;
      if(pos <= mid) update(u << 1,l,mid,pos,k);
      else update(u << 1 | 1,mid + 1,r,pos,k);
      t[u] = t[u << 1] + t[u << 1 | 1];
  }
  int ask(int u,int l,int r,int L,int R) {
      if(l > R || r < L) return 0;
      if(L <= l && r <= R) return t[u];
      int mid = l + r >> 1;
      return (ask(u << 1,l,mid,L,R) + ask(u << 1 | 1,mid + 1,r,L,R));
  }    
}T[2];
int main() {
  n = read();int Q = read();
  for(int i = 1;i <= n;i++) val[i] = read();
  for(int i = 1,a,b;i < n;i++) {
      a = read();b = read();
      add(a,b);add(b,a);
  }
  dfs(1,0,1);
  n++;
  while(Q--) {
      int opt = read();
      if(opt == 2) {
          int x = read();
          printf("%d\n",val[x] + T[col[x]].ask(1,1,n,1,L[x]) - T[1-col[x]].ask(1,1,n,1,L[x]));
      }
      else {
          int x = read(),y = read();
          T[col[x]].update(1,1,n,L[x],y);
          T[col[x]].update(1,1,n,R[x] + 1,-y);
      }
  }
}

[USACO19DEC]Bessie's Snow Cow P

个人觉得不错的一道题目，比较综合，要考虑 序上的差分，建议画个图理解一下。

分析

我们查询答案时，我们有两种答案。一是，全部覆盖了子树的答案，二是，只覆盖了一部分子树的答案。所以我们可以对这两种答案分别开一个树状数组维护。而修改操作就可以对每个颜色开一个 ，每次修改到他的父亲，那么它的贡献就可以减去。那么总复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100,inf = 0x3f3f3f3f;
#define ll long long 
int read() {int x;scanf("%d",&x);return x;}
struct Edge {int to,nxt;}e[N << 1];
set<int> s[N];
#define It set<int>::iterator
int n,head[N],ecnt,id[N],rid[N],Id,si[N];
void add(int x,int y) {e[++ecnt]=(Edge){y,head[x]};head[x] = ecnt;}
struct Bit {
    ll t[N];
    void upd(int a,ll d) {for(int i = a;i <= n;i += i & -i) t[i] += d;}
    ll ask(int a) {ll tot = 0;for(int i = a;i;i -= i & -i) tot += t[i];return tot;}
}A,B;
void dfs(int x) {
    rid[id[x] = ++Id] = x;si[x] = 1;for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;if(id[y]) continue;dfs(y); si[x] += si[y];
    }
}
void upd(int x,int d) {
//    cout << x << " " << d << endl;
    A.upd(id[x],d);
    A.upd(id[x] + si[x],-d);
    B.upd(id[x],si[x] * d);
}
bool in(int a,int b) {return si[a] + id[a] <= si[b] + id[b];}
int main() {
    n = read();int Q = read();
    for(int i = 1,a,b;i < n;i++) {
        a = read();b = read();
        add(a,b);add(b,a);
    }
    dfs(1);
//    cout << "debug1 " << endl;
    while(Q--) {
        int opt = read();
        if(opt == 1) {
            int x = read(),y = read();
            It it = s[y].lower_bound(id[x]);
            if(it != s[y].begin()) {
                It itl = it;itl--; 
                if(in(x,rid[*itl])) continue;
            }
            while(it != s[y].end() && (*it) <= si[x] + id[x] - 1) {
//                cout << (*it) << endl;
                upd(rid[(*it)],-1);s[y].erase(it++);
            }
            s[y].insert(id[x]);upd(x,1);
        }
        else {
            int x = read();
            ll ans = si[x] * A.ask(id[x]) + B.ask(id[x] + si[x] - 1) - B.ask(id[x]);
            printf("%lld\n",ans);
        }
    }
}

结语

序强大在于它将一个树转化为一个序列，使我们的操作更加简便。其实还有许多题目可以用到 序，而且像树链剖分这种算法就是基于 序实现的。反正就是很重要了。