树上启发式合并(DSU-on-Tree)

前言

树上启发式合并，用来解决子树查询问题，是一种离线的、“暴力的”算法。从某种角度而言，与莫队算法有些类似，即：按照我们指定的顺序对数据做一个遍历，在遍历过程中记录询问的答案。CF上有一个专门的blog，讲了很多，本文只涉及到有关轻重链剖分的部分。oi-wiki上有一个更短的文章。

简单而言，就是对每一个节点，分两步：

1. 递归统计子节点的数据
   • 先统计轻儿子（统计完的数据即刻清空）
   • 最后统计重儿子（统计完的数据保留下来）
2. 统计自己的数据（就是再统计一遍轻儿子的数据，加上本节点的数据）

在统计本节点的数据时，因为重儿子的数据已经保存，因此只需要再统计一遍轻儿子的数据，再加上本节点的数据，就有了本节点子树的所有数据，于是可以回答有关本节点子树的相关询问。

可以证明（并不会证明），这样重复统计以及清空操作，数量级是$O(N\log N)$的。

当然首先要会轻重链剖分，其实并不需要，因为这里其实并不需要实际剖出树链，只需要求出重儿子即可。因此实际上比剖分要简单的多。出于个人习惯，还是称之为剖分。

入门题

例1

为了简单起见，我们考虑一个不需要DSUonTree的问题，问子树的节点数量。这个显然$O(N)$就能完成。我们考虑一下启发式合并。

#include <bits/stdc++.h>
using namespace std;

struct dsu_on_tree_t{

using vi = vector<int>;

int N;
vector<vi> G; // 树, 1-index

struct node_t{ // 树链剖分的结构
    int size; 
    int hson; // 重儿子，这里是原树编号    
    int nid;  // 在树链剖分中的新编号
    int mdes; // 本子树全部在[nid, mdes]之间, 这是剖分编号
};
vector<node_t> Nodes;
vi New2Old;   // 剖分的编号为i，则原树节点编号为New2Old[i], 显然有Nodes[New2Old[i]].nid == i
int TimeStamp;
int Root;

vector<int> Ans;
int Cnt; // 全局变量用于记录即时数据

void init(int n){
    N = n;
    G.assign(N + 1, {});
    Nodes.assign(N + 1, {0, 0, 0, 0});
    New2Old.assign(N + 1, 0);
    TimeStamp = 0;

    Ans.assign(N + 1, 0);
}

void mkDiEdge(int a, int b){
    G[a].push_back(b);
}

void mkBiEdge(int a, int b){
    mkDiEdge(a, b);
    mkDiEdge(b, a);
}

void dfsHeavy(int u, int p){ // 递归重儿子
    auto & n = Nodes[u];
    n.size = 1;
    New2Old[n.nid = ++TimeStamp] = u;

    for(auto v : G[u]){
        if(v == p) continue;

        dfsHeavy(v, u);
        n.size += Nodes[v].size;
        if(Nodes[n.hson].size < Nodes[v].size) n.hson = v;
    }

    n.mdes = TimeStamp;
    return;
}


void dfs(int u, int p, bool keep){ // 递归
    const auto & n = Nodes[u];
    for(auto v : G[u]){
        if(v == p or v == n.hson) continue;
        dfs(v, u, false);
    }
    /// 最后递归重儿子
    if(n.hson) dfs(n.hson, u, true);

    /// 以下为统计u节点及其轻儿子
    if(n.hson){
        for(int i=n.nid;i<Nodes[n.hson].nid;++i) ++Cnt;
        /// 刚好把重儿子忽略掉
        for(int i=Nodes[n.hson].mdes+1;i<=n.mdes;++i) ++Cnt;
    }else{ // 只有一个节点
        ++Cnt;
    }

    /// 此时可以回答问题
    Ans[u] = Cnt;

    /// 是否清空u子树对即时数据的影响
    if(not keep){
        for(int i=n.nid;i<=n.mdes;++i) --Cnt;
    }
    return;
}


}Tree;

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    Tree.init(n);
    for(int a,i=2;i<=n;++i){
        cin >> a;
        Tree.mkDiEdge(a, i);
    }
    Tree.dfsHeavy(1, 0);
    Tree.dfs(1, 0, true);
    for(int i=1;i<=n;++i) cout << Tree.Ans[i] << "\n";
    return 0;
}

首先关于树链剖分部分，加了一个数据域mdes，其作用主要是为了明确本子树的范围。这样方便后续将代码写成迭代实现。树链剖分的实现这里就略过了。

然后就是本文的核心实现函数dfs。
这一部分就是递归，并且把重儿子放在最后递归。

    for(auto v : G[u]){
        if(v == p or v == n.hson) continue;
        dfs(v, u, false);
    }
    /// 最后递归重儿子
    if(n.hson) dfs(n.hson, u, true);

接下来就是统计即时数据，即统计u子树中除了u的重儿子之外的节点对即时数据造成的影响。因为记录了mdes，这一段可以写成迭代。迭代实现对于初次实现本算法的程序员，在调试方面比较友好。当然，也可以写成递归实现。

    /// 以下为统计u节点及其轻儿子
    if(n.hson){
        for(int i=n.nid;i<Nodes[n.hson].nid;++i) ++Cnt;
        /// 刚好把重儿子忽略掉
        for(int i=Nodes[n.hson].mdes+1;i<=n.mdes;++i) ++Cnt;
    }else{ // 只有一个节点
        ++Cnt;
    }

接下来是根据当前的即时数据，回答跟u有关的问题。这里的话比较简单。

    /// 此时可以回答问题
    Ans[u] = Cnt;

最后是根据参数，决定是否要清空u子树对即时数据的影响。这里写成迭代就非常自然了。当然，递归也是极好的。

    /// 是否清空u子树对即时数据的影响
    if(not keep){
        for(int i=n.nid;i<=n.mdes;++i) --Cnt;
    }

对于DSU-on-Tree而言，这个流程是固定的。只需要考虑每个节点对即时数据造成的影响，以及如何根据即时数据回答问题即可。当然这两个动作需要能够“很快的”完成。

例2

再来看标准的例子，每个节点有一个颜色，问子树的不同颜色的种类的数量。只需要有一个计数器记录各种颜色的数量，并且记录计数器中不同种类的数量即可，都可以在$O(1)$完成。因此假设DSU的流程，在$O(N\log N)$可以完成。

#include <bits/stdc++.h>
using namespace std;

struct dsu_on_tree_t{

using vi = vector<int>;

int N;
vector<vi> G; // 树, 1-index

struct node_t{ // 树链剖分的结构
    int size; 
    int hson; // 重儿子，这里是原树编号    
    int nid;  // 在树链剖分中的新编号
    int mdes; // 本子树全部在[nid, mdes]之间, 这是剖分编号
};
vector<node_t> Nodes;
vi New2Old;   // 剖分的编号为i，则原树节点编号为New2Old[i], 显然有Nodes[New2Old[i]].nid == i
int TimeStamp;
int Root;

vector<int> Color;

vector<int> Flag;
int Cnt; // 全局变量用于记录即时数据

vector<int> Ans;
vector<vi> Questions;

void init(int n){
    N = n;
    G.assign(N + 1, {});
    Nodes.assign(N + 1, {0, 0, 0, 0});
    New2Old.assign(N + 1, 0);
    TimeStamp = 0;
    Color.assign(N + 1, 0);

    Flag.assign(N + 1, Cnt = 0);
}

void mkDiEdge(int a, int b){
    G[a].push_back(b);
}

void mkBiEdge(int a, int b){
    mkDiEdge(a, b);
    mkDiEdge(b, a);
}

void dfsHeavy(int u, int p){ // 递归重儿子
    auto & n = Nodes[u];
    n.size = 1;
    New2Old[n.nid = ++TimeStamp] = u;

    for(auto v : G[u]){
        if(v == p) continue;

        dfsHeavy(v, u);
        n.size += Nodes[v].size;
        if(Nodes[n.hson].size < Nodes[v].size) n.hson = v;
    }

    n.mdes = TimeStamp;
    return;
}


void dfs(int u, int p, bool keep){ // 递归
    const auto & n = Nodes[u];
    for(auto v : G[u]){
        if(v == p or v == n.hson) continue;
        dfs(v, u, false);
    }
    /// 最后递归重儿子
    if(n.hson) dfs(n.hson, u, true);

    /// 以下为统计u节点及其轻儿子
    if(n.hson){
        for(int i=n.nid;i<Nodes[n.hson].nid;++i){
            if(1 == ++Flag[Color[New2Old[i]]]){
                ++Cnt;
            }
        }
        for(int i=Nodes[n.hson].mdes+1;i<=n.mdes;++i){
            if(1 == ++Flag[Color[New2Old[i]]]){
                ++Cnt;
            }
        }
    }else{ // 只有一个节点
        if(1 == ++Flag[Color[u]]){
            ++Cnt;
        }
    }

    /// 此时可以回答问题
    for(auto i : Questions[u]){
        Ans[i] = Cnt;
    }

    /// 是否清空u子树对即时数据的影响
    if(not keep){
        for(int i=n.nid;i<=n.mdes;++i) {
            if(0 == --Flag[Color[New2Old[i]]]){
                --Cnt;
            }
        }
    }
    return;
}


}Tree;

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    Tree.init(n);
    for(int a,b,i=2;i<=n;++i){
        cin >> a >> b;
        Tree.mkBiEdge(a, b);
    }
    for(int i=1;i<=n;++i) cin >>Tree.Color[i];

    int q; cin >> q;
    Tree.Questions.assign(n + 1, {});
    Tree.Ans.assign(q, {});
    for(int a,i=0;i<q;++i){
        cin >> a;
        Tree.Questions[a].push_back(i);
    } 

    Tree.dfsHeavy(1, 0);
    Tree.dfs(1, 0, true);
    for(auto i : Tree.Ans) cout << i << "\n";
    return 0;
}

NC23807的题目意思与本题是一模一样的，这里就不再赘述。

例3CF600E

这也是一个入门的例子，可以更好的认识清空操作的含义。给定树，每个节点有颜色。询问每一个子树的颜色的众数，即求出出现颜色最多的颜色编号；如果有多个颜色均出现最多次，则对编号求和。

本题显然也要弄一个计数器，然后每过一个节点，相应的颜色数量加加即可，对于众数或者众数求和都很简单。可能存在的一个问题在于如何清空？如果要考虑移除一个节点，对于答案的影响，那就很难办了。因为最值不支持快速的减法操作。但是注意到，本质上我们进行的是一个清空操作。考虑到递归顺序的安排，每次需要清空时，我们必然处在轻儿子处，且相应的重儿子必然在其之后。因此当本次清空完成时，实际上所有即时数据全部都清零了。之所以有些数据需要逐个节点、逐个节点的操作，是为了控制时间，只清除非零的数据。因为如果不管三七二十一，直接fill所有数据，显然是要超时的。

#include <bits/stdc++.h>
using namespace std;

struct dsu_on_tree_t{

using vi = vector<int>;

int N;
vector<vi> G; // 树, 1-index

struct node_t{ // 树链剖分的结构
    int size; 
    int hson; // 重儿子，这里是原树编号    
    int nid;  // 在树链剖分中的新编号
    int mdes; // 本子树全部在[nid, mdes]之间, 这是剖分编号
};
vector<node_t> Nodes;
vi New2Old;   // 剖分的编号为i，则原树节点编号为New2Old[i], 显然有Nodes[New2Old[i]].nid == i
int TimeStamp;
int Root;

vector<int> Color;

vector<int> Flag;

vector<long long> Ans;

int MaxCnt;
long long NowAns;

void init(int n){
    N = n;
    G.assign(N + 1, {});
    Nodes.assign(N + 1, {0, 0, 0, 0});
    New2Old.assign(N + 1, 0);
    TimeStamp = 0;
    Color.assign(N + 1, 0);

    Flag.assign(N + 1, MaxCnt = NowAns = 0);
    Ans.assign(N, 0);
}

void mkDiEdge(int a, int b){
    G[a].push_back(b);
}

void mkBiEdge(int a, int b){
    mkDiEdge(a, b);
    mkDiEdge(b, a);
}

void dfsHeavy(int u, int p){ // 递归重儿子
    auto & n = Nodes[u];
    n.size = 1;
    New2Old[n.nid = ++TimeStamp] = u;

    for(auto v : G[u]){
        if(v == p) continue;

        dfsHeavy(v, u);
        n.size += Nodes[v].size;
        if(Nodes[n.hson].size < Nodes[v].size) n.hson = v;
    }

    n.mdes = TimeStamp;
    return;
}


void dfs(int u, int p, bool keep){ // 递归
    const auto & n = Nodes[u];
    for(auto v : G[u]){
        if(v == p or v == n.hson) continue;
        dfs(v, u, false);
    }
    /// 最后递归重儿子
    if(n.hson) dfs(n.hson, u, true);

    /// 以下为统计u节点及其轻儿子
    if(n.hson){
        for(int i=n.nid;i<Nodes[n.hson].nid;++i){
            auto c = ++Flag[Color[New2Old[i]]];
            if(c > MaxCnt) MaxCnt = c, NowAns = Color[New2Old[i]];
            else if(c == MaxCnt) NowAns += Color[New2Old[i]];
        }
        for(int i=Nodes[n.hson].mdes+1;i<=n.mdes;++i){
            auto c = ++Flag[Color[New2Old[i]]];
            if(c > MaxCnt) MaxCnt = c, NowAns = Color[New2Old[i]];
            else if(c == MaxCnt) NowAns += Color[New2Old[i]];
        }
    }else{ // 只有一个节点
        Flag[NowAns = Color[u]] = MaxCnt = 1;
    }

    /// 此时可以回答问题
    Ans[u - 1] = NowAns;

    /// 是否清空u子树对即时数据的影响
    if(not keep){
        /// 注意这里是清空，因此可以直接令全局变量为零
        MaxCnt = NowAns = 0;
        for(int i=n.nid;i<=n.mdes;++i) {
            Flag[Color[New2Old[i]]] = 0;
            /// 一般习惯写成减减，但实际上直接清零也可以
            // --Flag[Color[New2Old[i]]];
        }
    }
    return;
}


}Tree;

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    Tree.init(n);
    for(int i=1;i<=n;++i) cin >>Tree.Color[i];
    for(int a,b,i=2;i<=n;++i){
        cin >> a >> b;
        Tree.mkBiEdge(a, b);
    }
    
    Tree.dfsHeavy(1, 0);
    Tree.dfs(1, 0, true);
    for(auto i : Tree.Ans) cout << i << " ";
    cout << endl;
    return 0;
}

这里统计答案的关键就在于清空的位置，一般习惯碰上计数器都是写减减，肯定不会有问题。但实际上直接把计数器清零也可以，因为这里其实不是清除单个节点对即时数据的影响，而是清空整个子树对即时数据的影响。又由于轻、重的递归顺序，因此清空轻儿子的效果实际上就是清空整个数据。因此这个操作才可以直接进行：MaxCnt = NowAns = 0;。同样的计数器数组也可以直接清零。之所以不用fill(Flag.begin(),Flag.end(),0)只是因为会超时。

CF570D

给定树，节点上有字符，有若干个询问(v, h)，问子树v上深度为h的节点是否能够通过重排序构成回文串。注意节点深度是指整个树上的深度，因此是固定的。实际上就是问对应节点的字符数量，是否奇数个字母的数量少于等于1。由于只涉及到奇偶，可以使用一个26位二进制数表示数量，只需检查1的位数小于等于1即可。令cnt[d]表示表示深度为d的情况下的字符数量，使用DSU来维护cnt数组。然后对每个子树u，如果有关于它的问题，例如(u, h)，则查询当时的cnt[h]、且记录下来即可。与前几题的区别，简而言之前几题使用了权值计数器，这里使用了深度计数器。

#include <bits/stdc++.h>
using namespace std;

struct dsu_on_tree_t{

using vi = vector<int>;

int N;
vector<vi> G; // 树, 1-index

struct node_t{ // 树链剖分的结构
    int size; 
    int hson; // 重儿子，这里是原树编号    
    int nid;  // 在树链剖分中的新编号
    int mdes; // 本子树全部在[nid, mdes]之间, 这是剖分编号
};
vector<node_t> Nodes;
vi New2Old;   // 剖分的编号为i，则原树节点编号为New2Old[i], 显然有Nodes[New2Old[i]].nid == i
int TimeStamp;
int Root;
vector<int> Depth;

string S;
vector<int> Ans;

vector<vector<pair<int, int>>> Questions;

vector<int> Cnt;

void init(int n){
    N = n;
    G.assign(N + 1, {});
    Nodes.assign(N + 1, {0, 0, 0, 0});
    New2Old.assign(N + 1, 0);
    TimeStamp = 0;
    Depth.assign(N + 1, 0);
    Cnt.assign(N + 1, 0);
}

void mkDiEdge(int a, int b){
    G[a].push_back(b);
}

void mkBiEdge(int a, int b){
    mkDiEdge(a, b);
    mkDiEdge(b, a);
}

void dfsHeavy(int u, int p){ // 递归重儿子
    Depth[u] = Depth[p] + 1;
    auto & n = Nodes[u];
    n.size = 1;
    New2Old[n.nid = ++TimeStamp] = u;

    for(auto v : G[u]){
        if(v == p) continue;

        dfsHeavy(v, u);
        n.size += Nodes[v].size;
        if(Nodes[n.hson].size < Nodes[v].size) n.hson = v;
    }

    n.mdes = TimeStamp;
    return;
}


void dfs(int u, int p, bool keep){ // 递归
    const auto & n = Nodes[u];
    for(auto v : G[u]){
        if(v == p or v == n.hson) continue;
        dfs(v, u, false);
    }
    /// 最后递归重儿子
    if(n.hson) dfs(n.hson, u, true);

    /// 以下为统计u节点及其轻儿子
    if(n.hson){
        for(int i=n.nid;i<Nodes[n.hson].nid;++i){
            auto t = S[New2Old[i]] - 'a';
            Cnt[Depth[New2Old[i]]] ^= (1 << t);
        }
        for(int i=Nodes[n.hson].mdes+1;i<=n.mdes;++i){
            auto t = S[New2Old[i]] - 'a';
            Cnt[Depth[New2Old[i]]] ^= (1 << t);  
        }
    }else{ // 只有一个节点
        Cnt[Depth[u]] = 1 << (S[u] - 'a');
    }

    /// 此时可以回答问题
    for(const auto & pp : Questions[u]){
        auto h = pp.first;
        bool b = true;
        int c = 0;
        for(int i=0;i<26;++i){
            if((1 << i) & Cnt[h])if(++c > 1){b = false; break;}
        }
        Ans[pp.second] = b ? 1 : 0;
    }

    /// 是否清空u子树对即时数据的影响
    if(not keep){
        /// 清空
        for(int i=n.nid;i<=n.mdes;++i) {
            Cnt[Depth[New2Old[i]]] = 0;
        }
    }
    return;
}


}Tree;

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, q; cin >> n >> q;
    Tree.init(n);    
    for(int a,i=2;i<=n;++i){
        cin >> a;
        Tree.mkDiEdge(a, i);
    }
    cin >> Tree.S;
    Tree.S = " " + Tree.S;
    
    Tree.Questions.assign(n + 1, {});
    Tree.Ans.assign(q, 0);
    for(int u,h,i=0;i<q;++i){
        cin >> u >> h;
        Tree.Questions[u].emplace_back(h, i);
    }
    
    Tree.dfsHeavy(1, 0);
    Tree.dfs(1, 0, true);
    for(auto i : Tree.Ans) cout << (i ? "Yes\n" : "No\n");
    return 0;
}

CF246E是一个既有深度又有权值的题目，本质上就是询问子树u中深度为k的不同权值的数量。可以利用map作为计数器，在增加一个$\log$的情况下完成查询。

略复杂一点的题目

有了DSUonTree的基本流程，就可以把注意力集中在问题的转化与即时数据的快速维护上。只要能够在合理的时间复杂度内做到，就能解决整个问题。

CF208E

CF208E给定一个森林，定义父节点是子节点的一级祖先，类似可以定义k级祖先。如果两个节点u和v有一个共同的k级祖先，则它们互为k级兄弟。每次询问给定v和k，问v的k级兄弟有多少个。假设v的k级祖先是p，则等价于问p的k级子节点的数量。有了前面的关于深度相关计数器的经验，这个问题很容易解决。于是问题的关键变为了能否很快的知道任意节点的任意级祖先。这个显然是可以倍增解决的，与求$LCA$类似。因此先做一个预处理，将问题转化一下，然后DSU即可。

#include <bits/stdc++.h>
using namespace std;

int const LOGSZ = 17;

struct dsu_on_tree_t{

using vi = vector<int>;

int N;
vector<vi> G; // 树, 1-index

struct node_t{ // 树链剖分的结构
    int size; 
    int hson; // 重儿子，这里是原树编号    
    int nid;  // 在树链剖分中的新编号
    int mdes; // 本子树全部在[nid, mdes]之间, 这是剖分编号
};
vector<node_t> Nodes;
vi New2Old;   // 剖分的编号为i，则原树节点编号为New2Old[i], 显然有Nodes[New2Old[i]].nid == i
int TimeStamp;
int Root;
vector<int> Depth;
vector<vi> Parent;
vector<int> Log2;

vector<int> Ans;
vector<vector<pair<int, int>>> Questions;
vector<int> Cnt;

void init(int n){
    N = n;
    G.assign(N + 1, {});
    Nodes.assign(N + 1, {0, 0, 0, 0});
    New2Old.assign(N + 1, 0);
    TimeStamp = 0;
    Depth.assign(N + 1, 0);
    Parent.assign(N + 1, vi(LOGSZ, 0));
    Cnt.assign(N + 1, 0);

    Log2.assign(N + 1, 0);
    for(int i=1;i<=N;++i){
        Log2[i] = Log2[i - 1] + ((1 << Log2[i - 1]) == i ? 1 : 0);
    }
}

void mkDiEdge(int a, int b){
    G[a].push_back(b);
}

void mkBiEdge(int a, int b){
    mkDiEdge(a, b);
    mkDiEdge(b, a);
}

void dfsHeavy(int u, int p){ // 递归重儿子
    Depth[u] = Depth[p] + 1;
    auto & n = Nodes[u];
    n.size = 1;
    New2Old[n.nid = ++TimeStamp] = u;
    Parent[u][0] = p;
    for(int i=1;i<=Log2[Depth[u]];++i){
        Parent[u][i] = Parent[Parent[u][i - 1]][i - 1];
    }

    for(auto v : G[u]){
        if(v == p) continue;

        dfsHeavy(v, u);
        n.size += Nodes[v].size;
        if(Nodes[n.hson].size < Nodes[v].size) n.hson = v;
    }

    n.mdes = TimeStamp;
    return;
}


void dfs(int u, int p, bool keep){ // 递归
    const auto & n = Nodes[u];
    for(auto v : G[u]){
        if(v == p or v == n.hson) continue;
        dfs(v, u, false);
    }
    /// 最后递归重儿子
    if(n.hson) dfs(n.hson, u, true);

    /// 以下为统计u节点及其轻儿子
    if(n.hson){
        for(int i=n.nid;i<Nodes[n.hson].nid;++i){
            ++Cnt[Depth[New2Old[i]]];
        }
        for(int i=Nodes[n.hson].mdes+1;i<=n.mdes;++i){
            ++Cnt[Depth[New2Old[i]]];
        }
    }else{ // 只有一个节点
        Cnt[Depth[u]] = 1;
    }

    /// 此时可以回答问题
    for(const auto & pp : Questions[u]){
        Ans[pp.second] = Cnt[pp.first + Depth[u]] - 1;
    }

    /// 是否清空u子树对即时数据的影响
    if(not keep){
        /// 清空
        for(int i=n.nid;i<=n.mdes;++i) {
            Cnt[Depth[New2Old[i]]] = 0;
        }
    }
    return;
}


}Tree;

vector<int> Root;

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    Root.clear();
    Root.reserve(n);

    Tree.init(n);    
    for(int a,i=1;i<=n;++i){
        cin >> a;
        if(a) Tree.mkDiEdge(a, i);
        else Root.push_back(i);
    }
    for(auto i : Root) Tree.dfsHeavy(i, 0);
   
    int q; cin >> q;
    Tree.Questions.assign(n + 1, {});
    Tree.Ans.assign(q, 0);
    for(int p,u,k,i=0;i<q;++i){
        cin >> u >> k;
        auto target = k;
        for(int i=LOGSZ-1;i>=0;--i){
            if((1 << i) & target){
                u = Tree.Parent[u][i];
            }
        }
        Tree.Questions[u].emplace_back(k, i);
    }
    
    for(auto i : Root) Tree.dfs(i, 0, false);
    for(auto i : Tree.Ans) cout << (i) << " ";
    cout << endl;
    return 0;
}

NC235719

这个题目可以更好的展示DSUonTree的框架作用。每次回答询问[u,a,b]，即u子树内深度在[a,b]区间内的所有节点的权值的最小值、最大值与和。这个明显是一个区间查询问题，再考虑到DSUonTree的统计过程，因此我们需要解决一个单点变动、区间查询的任务，因为要查询最值，所以使用线段树。如果不考虑线段树的部分，可以看到与DSUonTree有关的流程与之前的代码并无区别。

#include <bits/stdc++.h>
using namespace std;

using llt = long long;
llt const INF = 0x1F2F3F4F5F6F7F8F;
llt const NINF = -INF;

struct SegTree{ // 线段树带延迟

using llt = long long;

int N;

using value_type = array<llt, 3>; // 最小值，最大值，和
vector<value_type> data; // 线段树

using lazy_type = pair<llt, int>; 
vector<lazy_type> lazy; // 延迟标记

/// 从下往上计算信息，要变动
value_type _up_(const value_type & ls, const value_type & rs) {
    // assert(0);
    return {min(ls[0], rs[0]), max(ls[1], rs[1]), ls[2] + rs[2]};
}

/// 从上往下计算信息，要变动
void _dn_(int t, int s, int e, const lazy_type & delta) {
    // assert(0);
    if(delta.second == -1){ // 清零操作
        data[t] = value_zero();        
    }else if(delta.second == 1){ // 增加一个权值， 必然是单点操作
        data[t][0] = min(data[t][0], delta.first);
        data[t][1] = max(data[t][1], delta.first);
        data[t][2] += delta.first;
    }
    return;
}

/// 初始化，清零，不用动
void init(int n) {
    data.assign((N = n) + 1 << 2, value_zero());
    // lazy.assign(n + 1 << 2, lazy_zero());
}

/// 这个函数不用动
void modify(int a, int b, const lazy_type & delta){
    _modify(1, 1, N, a, b, delta);
}

/// 这个函数不用动
value_type query(int a, int b){
    return _query(1, 1, N, a, b);
}

/// 几乎不用动
value_type _query(int t, int s, int e, int a, int b) {
    if(a <= s and e <= b) {
        return data[t];
    }
    // _pushDown(t, s, e);
    int mid = (s + e) >> 1;
    value_type ans = value_zero(); // 如果求最值，这里不能用zero
    if(a <= mid) ans = _up_(ans, _query(lson(t), s, mid, a, b));
    if(mid < b) ans = _up_(ans, _query(rson(t), mid + 1, e, a, b));
    return ans;
}

/// 几乎不用动
void _modify(int t, int s, int e, int a, int b, const lazy_type & delta) {
    if(a <= s and e <= b) {
        _dn_(t, s, e, delta);
        return;
    }
    // _pushDown(t, s, e);
    int mid = (s + e) >> 1;
    if(a <= mid) _modify(lson(t), s, mid, a, b, delta);
    if(mid < b) _modify(rson(t), mid + 1, e, a, b, delta);
    _pushUp(t);
    return;
}

/// 这个函数不用动
void _pushUp(int t) {
    data[t] = _up_(data[lson(t)], data[rson(t)]);
}

/// 辅助函数，视延迟的类型而变动
static const lazy_type & lazy_zero() {
    static const lazy_type LAZY0 = {0, 0};
    return LAZY0; 
}

/// 辅助函数，视线段树信息类型而变动
static const value_type & value_zero() {
    static const value_type VALUE0 = {INF, NINF, 0LL};
    return VALUE0;
}

/// 这两个函数不用变动
static int lson(int x) {return x << 1;}
static int rson(int x) {return lson(x) | 1;}


};


struct dsu_on_tree_t{

using vi = vector<int>;

int N;
vector<vi> G; // 树, 1-index

struct node_t{ // 树链剖分的结构
    int size; 
    int hson; // 重儿子，这里是原树编号    
    int nid;  // 在树链剖分中的新编号
    int mdes; // 本子树全部在[nid, mdes]之间, 这是剖分编号
};
vector<node_t> Nodes;
vi New2Old;   // 剖分的编号为i，则原树节点编号为New2Old[i], 显然有Nodes[New2Old[i]].nid == i
int TimeStamp;
int Root;
vector<int> Depth;
SegTree St;
vector<long long> W;

vector<array<llt, 3>> Ans;
vector<vector<array<int, 3>>> Questions;

void init(int n){
    N = n;
    G.assign(N + 1, {});
    Nodes.assign(N + 1, {0, 0, 0, 0});
    New2Old.assign(N + 1, 0);
    TimeStamp = 0;
    Depth.assign(N + 1, 0);
    W.assign(N + 1, 0);
    St.init(N);
}

void mkDiEdge(int a, int b){
    G[a].push_back(b);
}

void mkBiEdge(int a, int b){
    mkDiEdge(a, b);
    mkDiEdge(b, a);
}

void dfsHeavy(int u, int p){ // 递归重儿子
    Depth[u] = Depth[p] + 1;
    auto & n = Nodes[u];
    n.size = 1;
    New2Old[n.nid = ++TimeStamp] = u;

    for(auto v : G[u]){
        if(v == p) continue;

        dfsHeavy(v, u);
        n.size += Nodes[v].size;
        if(Nodes[n.hson].size < Nodes[v].size) n.hson = v;
    }

    n.mdes = TimeStamp;
    return;
}


void dfs(int u, int p, bool keep){ // 递归
    const auto & n = Nodes[u];
    for(auto v : G[u]){
        if(v == p or v == n.hson) continue;
        dfs(v, u, false);
    }
    /// 最后递归重儿子
    if(n.hson) dfs(n.hson, u, true);

    /// 以下为统计u节点及其轻儿子
    if(n.hson){
        for(int i=n.nid;i<Nodes[n.hson].nid;++i){
            St.modify(Depth[New2Old[i]], Depth[New2Old[i]], {W[New2Old[i]], 1});
        }
        for(int i=Nodes[n.hson].mdes+1;i<=n.mdes;++i){
            St.modify(Depth[New2Old[i]], Depth[New2Old[i]], {W[New2Old[i]], 1});
        }
    }else{ // 只有一个节点
        St.modify(Depth[u], Depth[u], {W[u], 1});
    }

    /// 此时可以回答问题
    for(const auto & pp : Questions[u]){
        Ans[pp[2]] = St.query(Depth[u] + pp[0], Depth[u] + pp[1]);
    }

    /// 是否清空u子树对即时数据的影响
    if(not keep){
        /// 清空
        for(int i=n.nid;i<=n.mdes;++i){
            St.modify(Depth[New2Old[i]], Depth[New2Old[i]], {0LL, -1});
        }
    }
    return;
}


}Tree;

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;

    Tree.init(n);   
    for(int i=1;i<=n;++i) cin >> Tree.W[i];
    for(int a,b,i=1;i<n;++i){
        cin >> a >> b;
        Tree.mkBiEdge(a, b);
    }
    
   
    int q; cin >> q;
    Tree.Questions.assign(n + 1, {});
    Tree.Ans.assign(q, {});
    for(int u,a,b,i=0;i<q;++i){
        cin >> u >> a >> b;
        Tree.Questions[u].push_back({a, b, i});
    }
    
    Tree.dfsHeavy(1, 0);
    Tree.dfs(1, 0, true);
    for(const auto & i : Tree.Ans) cout << i[0] << " " << i[1] << " " << i[2] << "\n";
    return 0;
}

这道题还可以用来验证清空流程。上文说过对于需要清空的情况，实际上就是清空整个即时数据，之前之所以不这么做，只是因为超时。现在既然已经用上了线段树，可以再往里加点料，即支持延迟操作。这样的话直接清空整个线段树就没有压力了。

#include <bits/stdc++.h>
using namespace std;

using llt = long long;
llt const INF = 0x1F2F3F4F5F6F7F8F;
llt const NINF = -INF;

struct SegTree{ // 线段树带延迟

using llt = long long;

int N;

using value_type = array<llt, 3>; // 最小值，最大值，和
vector<value_type> data; // 线段树

using lazy_type = pair<llt, int>; 
vector<lazy_type> lazy; // 延迟标记

/// 从下往上计算信息，要变动
value_type _up_(const value_type & ls, const value_type & rs) {
    // assert(0);
    return {min(ls[0], rs[0]), max(ls[1], rs[1]), ls[2] + rs[2]};
}

/// 从上往下计算信息，要变动
void _dn_(int t, int s, int e, const lazy_type & delta) {
    // assert(0);
    if(delta.second == -1){ // 清零操作
        data[t] = value_zero();      
        lazy[t] = delta;  
    }else if(delta.second == 1){ // 增加一个权值， 必然是单点操作
        data[t][0] = min(data[t][0], delta.first);
        data[t][1] = max(data[t][1], delta.first);
        data[t][2] += delta.first;
    }    
    return;
}

/// 初始化，清零，不用动
void init(int n) {
    data.assign((N = n) + 1 << 2, value_zero());
    lazy.assign(n + 1 << 2, lazy_zero());
}

/// 这个函数不用动
void modify(int a, int b, const lazy_type & delta){
    _modify(1, 1, N, a, b, delta);
}

/// 这个函数不用动
value_type query(int a, int b){
    return _query(1, 1, N, a, b);
}

/// 几乎不用动
value_type _query(int t, int s, int e, int a, int b) {
    if(a <= s and e <= b) {
        return data[t];
    }
    _pushDown(t, s, e);
    int mid = (s + e) >> 1;
    value_type ans = value_zero(); // 如果求最值，这里不能用zero
    if(a <= mid) ans = _up_(ans, _query(lson(t), s, mid, a, b));
    if(mid < b) ans = _up_(ans, _query(rson(t), mid + 1, e, a, b));
    return ans;
}

/// 几乎不用动
void _modify(int t, int s, int e, int a, int b, const lazy_type & delta) {
    if(a <= s and e <= b) {
        _dn_(t, s, e, delta);
        return;
    }
    _pushDown(t, s, e);
    int mid = (s + e) >> 1;
    if(a <= mid) _modify(lson(t), s, mid, a, b, delta);
    if(mid < b) _modify(rson(t), mid + 1, e, a, b, delta);
    _pushUp(t);
    return;
}

/// 这个函数不用动
void _pushUp(int t) {
    data[t] = _up_(data[lson(t)], data[rson(t)]);
}

/// 这个函数几乎不用动
void _pushDown(int t, int s, int e) {
    if(lazy_zero() == lazy[t]) return;
    auto & lz = lazy[t];
    auto ls = lson(t), rs = rson(t);
    int mid = (s + e) >> 1;

    _dn_(ls, s, mid, lz);
    _dn_(rs, mid + 1, e, lz);

    lz = lazy_zero();
}

/// 辅助函数，视延迟的类型而变动
static const lazy_type & lazy_zero() {
    static const lazy_type LAZY0 = {0, 0};
    return LAZY0; 
}

/// 辅助函数，视线段树信息类型而变动
static const value_type & value_zero() {
    static const value_type VALUE0 = {INF, NINF, 0LL};
    return VALUE0;
}

/// 这两个函数不用变动
static int lson(int x) {return x << 1;}
static int rson(int x) {return lson(x) | 1;}


};


struct dsu_on_tree_t{

using vi = vector<int>;

int N;
vector<vi> G; // 树, 1-index

struct node_t{ // 树链剖分的结构
    int size; 
    int hson; // 重儿子，这里是原树编号    
    int nid;  // 在树链剖分中的新编号
    int mdes; // 本子树全部在[nid, mdes]之间, 这是剖分编号
};
vector<node_t> Nodes;
vi New2Old;   // 剖分的编号为i，则原树节点编号为New2Old[i], 显然有Nodes[New2Old[i]].nid == i
int TimeStamp;
int Root;
vector<int> Depth;
SegTree St;
vector<long long> W;

vector<array<llt, 3>> Ans;
vector<vector<array<int, 3>>> Questions;

void init(int n){
    N = n;
    G.assign(N + 1, {});
    Nodes.assign(N + 1, {0, 0, 0, 0});
    New2Old.assign(N + 1, 0);
    TimeStamp = 0;
    Depth.assign(N + 1, 0);
    W.assign(N + 1, 0);
    St.init(N);
}

void mkDiEdge(int a, int b){
    G[a].push_back(b);
}

void mkBiEdge(int a, int b){
    mkDiEdge(a, b);
    mkDiEdge(b, a);
}

void dfsHeavy(int u, int p){ // 递归重儿子
    Depth[u] = Depth[p] + 1;
    auto & n = Nodes[u];
    n.size = 1;
    New2Old[n.nid = ++TimeStamp] = u;

    for(auto v : G[u]){
        if(v == p) continue;

        dfsHeavy(v, u);
        n.size += Nodes[v].size;
        if(Nodes[n.hson].size < Nodes[v].size) n.hson = v;
    }

    n.mdes = TimeStamp;
    return;
}


void dfs(int u, int p, bool keep){ // 递归
    const auto & n = Nodes[u];
    for(auto v : G[u]){
        if(v == p or v == n.hson) continue;
        dfs(v, u, false);
    }
    /// 最后递归重儿子
    if(n.hson) dfs(n.hson, u, true);

    /// 以下为统计u节点及其轻儿子
    if(n.hson){
        for(int i=n.nid;i<Nodes[n.hson].nid;++i){
            St.modify(Depth[New2Old[i]], Depth[New2Old[i]], {W[New2Old[i]], 1});
        }
        for(int i=Nodes[n.hson].mdes+1;i<=n.mdes;++i){
            St.modify(Depth[New2Old[i]], Depth[New2Old[i]], {W[New2Old[i]], 1});
        }
    }else{ // 只有一个节点
        St.modify(Depth[u], Depth[u], {W[u], 1});
    }

    /// 此时可以回答问题
    for(const auto & pp : Questions[u]){
        Ans[pp[2]] = St.query(Depth[u] + pp[0], Depth[u] + pp[1]);
    }

    /// 是否清空u子树对即时数据的影响
    if(not keep){
        /// 清空
        St.modify(1, N, {0LL, -1});
    }
    return;
}


}Tree;

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;

    Tree.init(n);   
    for(int i=1;i<=n;++i) cin >> Tree.W[i];
    for(int a,b,i=1;i<n;++i){
        cin >> a >> b;
        Tree.mkBiEdge(a, b);
    }
    
   
    int q; cin >> q;
    Tree.Questions.assign(n + 1, {});
    Tree.Ans.assign(q, {});
    for(int u,a,b,i=0;i<q;++i){
        cin >> u >> a >> b;
        Tree.Questions[u].push_back({a, b, i});
    }
    
    Tree.dfsHeavy(1, 0);
    Tree.dfs(1, 0, true);
    for(const auto & i : Tree.Ans) cout << i[0] << " " << i[1] << " " << i[2] << "\n";
    return 0;
}

这份代码与上一份的区别，在DSUonTree的部分，就是这里：

    if(not keep){
        /// 清空
        St.modify(1, N, {0LL, -1});
    }

不再逐个逐个节点的清空，而是一次性的清空整个线段树（注意，其实无需找出本子树深度的区间进行清空，直接清空整个即可）。当然，相应的线段树部分需要支持延迟操作。

NC235715

给定一个树，每次询问(u, k)，即u子树内权值不大于k的节点数量。由于权值取值范围在$[1,10^6]$，因此可以直接使用树状数组进行计数。每增加一个节点u，就将W[u]加1。需要查询时，只需要查询$[1,k]$的区间和即可。清空还是一个个清空，将对应位置减一即可。

#include <bits/stdc++.h>
using namespace std;

using llt = long long;
llt const INF = 0x1F2F3F4F5F6F7F8F;
llt const NINF = -INF;

struct FenwickTree{ // 树状数组

using value_type = long long int;
using vec_type = vector<value_type>;

int n;
vec_type c;

FenwickTree() = default;

static int lowbit(int x){return x & -x;}

void init(int nn){this->c.assign((this->n=nn) + 1, 0);}

void modify(int pos, value_type delta){
    for(int i=pos;i<=this->n;i+=lowbit(i)) this->c[i] += delta;
}

value_type query(int pos)const{
    value_type ans = 0;
    for(int i=pos;i;i-=lowbit(i)) ans += this->c[i];
    return ans;
}

value_type query(int s, int e)const{return this->query(e) - this->query(s - 1);}

};



struct dsu_on_tree_t{

using vi = vector<int>;

int N;
vector<vi> G; // 树, 1-index

struct node_t{ // 树链剖分的结构
    int size; 
    int hson; // 重儿子，这里是原树编号    
    int nid;  // 在树链剖分中的新编号
    int mdes; // 本子树全部在[nid, mdes]之间, 这是剖分编号
};
vector<node_t> Nodes;
vi New2Old;   // 剖分的编号为i，则原树节点编号为New2Old[i], 显然有Nodes[New2Old[i]].nid == i
int TimeStamp;
int Root;

FenwickTree Bt;
vector<long long> W;

vector<int> Ans;
vector<vector<array<int, 2>>> Questions;

void init(int n){
    N = n;
    G.assign(N + 1, {});
    Nodes.assign(N + 1, {0, 0, 0, 0});
    New2Old.assign(N + 1, 0);
    TimeStamp = 0;
    W.assign(N + 1, 0);
    Bt.init(1000001);
}

void mkDiEdge(int a, int b){
    G[a].push_back(b);
}

void mkBiEdge(int a, int b){
    mkDiEdge(a, b);
    mkDiEdge(b, a);
}

void dfsHeavy(int u, int p){ // 递归重儿子
    // Depth[u] = Depth[p] + 1;
    auto & n = Nodes[u];
    n.size = 1;
    New2Old[n.nid = ++TimeStamp] = u;

    for(auto v : G[u]){
        if(v == p) continue;

        dfsHeavy(v, u);
        n.size += Nodes[v].size;
        if(Nodes[n.hson].size < Nodes[v].size) n.hson = v;
    }

    n.mdes = TimeStamp;
    return;
}


void dfs(int u, int p, bool keep){ // 递归
    const auto & n = Nodes[u];
    for(auto v : G[u]){
        if(v == p or v == n.hson) continue;
        dfs(v, u, false);
    }
    /// 最后递归重儿子
    if(n.hson) dfs(n.hson, u, true);

    /// 以下为统计u节点及其轻儿子
    if(n.hson){
        for(int i=n.nid;i<Nodes[n.hson].nid;++i){
            Bt.modify(W[New2Old[i]], 1);
        }
        for(int i=Nodes[n.hson].mdes+1;i<=n.mdes;++i){
            Bt.modify(W[New2Old[i]], 1);
        }
    }else{ // 只有一个节点
        Bt.modify(W[u], 1);
    }

    /// 此时可以回答问题
    for(const auto & pp : Questions[u]){
        Ans[pp[1]] = Bt.query(pp[0]);
    }

    /// 是否清空u子树对即时数据的影响
    if(not keep){
        /// 清空
        for(int i=n.nid;i<=n.mdes;++i){
            Bt.modify(W[New2Old[i]], -1);
        }
    }
    return;
}


}Tree;

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;

    Tree.init(n);   
    for(int i=1;i<=n;++i) cin >> Tree.W[i];
    for(int a,b,i=1;i<n;++i){
        cin >> a >> b;
        Tree.mkBiEdge(a, b);
    }
    
   
    int q; cin >> q;
    Tree.Questions.assign(n + 1, {});
    Tree.Ans.assign(q, {});
    for(int u,a,i=0;i<q;++i){
        cin >> u >> a;
        Tree.Questions[u].push_back({a, i});
    }
    
    Tree.dfsHeavy(1, 0);
    Tree.dfs(1, 0, true);
    for(const auto & i : Tree.Ans) cout << i << "\n";
    return 0;
}

小结

总体而言，DSUonTree提供了一个离线查询的框架，其基础复杂度为$O(N\log N)$。在此基础上需要解决数据的单点更新、按需查询以及清空三种操作。如果这三种操作都能在$\log N$及其以内时间完成，应该说DSUonTree就是可用的。