首页 学习笔记

# 前置芝士

  • 重链剖分（最好是熟练掌握）

  • 莫队（大概了解即可，有一点相似的思想）

  • dfs 序（可有可无，主要是为了加速，其实我就没写过 QwQQwQ）

# 主要思想

dsuontreedsu\ on\ tree 又名树上启发式合并

（其实是非常暴力的一个东西。）

# 用途

可处理树上的一些统计类型的问题。

如：

  1. 求子树中颜色最多的颜色编号之和，相同数量都要加上 CF600E Lomsat gelral

  2. 给一棵树，树上每个节点都有一个颜色，求已点 uu 为根的子树中，出现次数 >=k>= k 的颜色有多少种 CF375D Tree and Queries

  3. 给一棵树，每个点上都有一个字母，每次询问 a,ba, b，查询以 aa 为根的子树内深度为 bb 的结点上的字母重新排列之后是否能构成回文串 CF570D Tree Requests

  4. 给你一片森林，每次询问一个点与多少个点拥有共同的 KK 级祖先 CF208E Blood Cousins

# 过程

先把处理所有已 uu 为根的所有轻儿子，并统计答案。

然后删除这些轻儿子的贡献，再把重儿子加进去。

然后不用删除，直接向上传到父亲节点，也就是 uu 节点即可。

怎么样，是不是听着感觉很暴力，但由于我们最后重儿子是直接继承上去的，所以复杂度可以控制在 loglog 内（跟树链剖分差不多）。

# 核心代码

# dfs

用来预处理出子树大小，重儿子的信息。

与树链剖分中的代码一模一样，不贴了。

# update

用于添加新的信息，或是删除不需要的信息。

mark
inline void update(ll x, ll fa, ll type){//type = 0，添加    type = 1，删除
    if(!type) add(x);
    else del(x);
    for(ri i = head[x]; i; i = edge[i].nxt){
        ll y = edge[i].v;
        if(y != fa) update(y, x, type);
    }
}

# solve

这个是树上启发式合并的核心部分。

第一种（推荐）：

inline void solve(int x, int typ){//typ = 0 ? 轻儿子：重儿子
    for(auto y : g[x]){
        if(y == fa[x] || y == son[x]) continue;
        solve(y, 0), res = mx = 0;// 递归处理轻儿子，删除信息
    }
    if(son[x]) solve(son[x], 1);// 处理重儿子
    for(auto y : g[x])
        if(y != fa[x] && y != son[x]) calc(y, 0);// 合并轻儿子
    add(x), ans[x] = res;// 把 x 加进去，更新答案
    if(!typ) calc(x, 1);// 如果当前是轻子树，删除数据
}

第二种：

inline void solve(ll x, ll fa){
    for(ri i = head[x]; i; i = edge[i].nxt){
        ll y = edge[i].v;
        if(y == fa || y == son[x]) continue;
        solve(y, x);// 递归处理
        update(y, x, 1);// 删去轻儿子
        sum = maxs = 0;// 清空变量
    }
    sum = maxs = 0;
    if(son[x]) solve(son[x], x);// 处理重儿子
    add(x);// 加上重儿子
    for(ri i = head[x]; i; i = edge[i].nxt){
        ll y = edge[i].v;
        if(y == fa || y == son[x]) continue;
        update(y, x, 0);// 加上轻儿子
    }
    ...// 更新答案
}

添加和删除操作类似于莫队，可以根据下面例题来理解。

# 例题

# 1. CF600E Lomsat gelral

最板子的一道题了。上面核心代码就是从这道题里复制出来的

话不多说，直接看代码吧，可以看上面的注释。

第一种：

#include <bits/stdc++.h>
#define pb push_back
#define pc putchar
#define int long long
using namespace std;
namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }
    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 1e5 + 10;
int n;
int col[N], siz[N], son[N], fa[N];
vector <int> g[N];
inline void dfs(int x, int f){
    siz[x] = 1, fa[x] = f;
    for(auto y : g[x]){
        if(y == f) continue;
        dfs(y, x), siz[x] += siz[y];
        if(siz[y] > siz[son[x]]) son[x] = y;
    }
}
int cnt[N], res, mx;
int ans[N];
inline void add(int x){
    cnt[col[x]]++;
    if(cnt[col[x]] > mx) mx = cnt[col[x]], res = col[x];
    else if(cnt[col[x]] == mx) res += col[x];
}
inline void del(int x){
    cnt[col[x]]--;
}
inline void calc(int x, int typ){
    !typ ? add(x) : del(x);
    for(auto y : g[x])
        if(y != fa[x]) calc(y, typ);
}
inline void solve(int x, int typ){
    for(auto y : g[x]){
        if(y == fa[x] || y == son[x]) continue;
        solve(y, 0), res = mx = 0;
    }
    if(son[x]) solve(son[x], 1);
    for(auto y : g[x])
        if(y != fa[x] && y != son[x]) calc(y, 0);
    add(x), ans[x] = res;
    if(!typ) calc(x, 1);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read();
    for(int i = 1; i <= n; ++i) col[i] = read();
    for(int i = 1; i < n; ++i){
        int u = read(), v = read();
        g[u].pb(v), g[v].pb(u);
    }
    dfs(1, 0), solve(1, 0);
    for(int i = 1; i <= n; ++i) write(ans[i]), pc(' ');
    return 0;
}
第二种：
mark
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ri register int
#define ll long long
using namespace std;
inline ll read(){
    ll x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x;
}
const ll N = 1e5 + 10;
ll n;
ll a[N];
struct node{
    ll v, nxt;
}edge[N << 1];
ll head[N], tot;
ll son[N], siz[N], cnt[N];
ll maxs, sum;
inline void add(ll x, ll y){
    edge[++tot] = (node){y, head[x]};
    head[x] = tot;
}
inline void dfs(ll x, ll fa){
    siz[x] = 1;
    for(ri i = head[x]; i; i = edge[i].nxt){
        ll y = edge[i].v;
        if(y == fa) continue;
        dfs(y, x);
        siz[x] += siz[y];
        if(!son[x] || siz[son[x]] < siz[y])
            son[x] = y;
    }
}
inline void add(ll x){
    cnt[a[x]]++;
    ll res = cnt[a[x]];// 顺便，更新出现次数最多的颜色，以及权值和。
    if(res > maxs) maxs = res, sum = a[x];
    else if(res == maxs) sum += a[x];
}
inline void del(ll x){
    cnt[a[x]]--;
}
inline void update(ll x, ll fa, ll type){
    if(!type) add(x);
    else del(x);
    for(ri i = head[x]; i; i = edge[i].nxt){
        ll y = edge[i].v;
        if(y != fa) update(y, x, type);
    }
}
ll ans[N];
inline void solve(ll x, ll fa){
    for(ri i = head[x]; i; i = edge[i].nxt){
        ll y = edge[i].v;
        if(y == fa || y == son[x]) continue;
        solve(y, x);
        update(y, x, 1);
        sum = maxs = 0;
    }
    sum = maxs = 0;
    if(son[x]) solve(son[x], x);
    add(x);
    for(ri i = head[x]; i; i = edge[i].nxt){
        ll y = edge[i].v;
        if(y == fa || y == son[x]) continue;
        update(y, x, 0);
    }
    ans[x] = sum;// 更新答案
}
signed main(){
    n = read();
    for(ri i = 1; i <= n; ++i)
        a[i] = read();
    for(ri i = 1; i < n; ++i){
        ll u = read(), v = read();
        add(u, v), add(v, u);
    }
    dfs(1, 0);
    solve(1, 0);
    for(ri i = 1; i <= n; ++i)
        printf("%lld ", ans[i]);
    puts("");
    return 0;
}
# 2. CF375D Tree and Queries
那我们发现这道题和例一似乎没什么区别……
先开个颜色桶，然后再对颜色出现次数做个类似于前缀和的东西，就是每次更新颜色出现次数的时候，令记录出现次数的桶 ++++。
直接看代码吧。
mark
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n, m, k;
int c[N], siz[N], son[N];
struct Query{
    int id, k;
};
vector <Query> g[N];
struct node{
    int v, nxt;
}edge[N << 1];
int head[N], tot;
int cnt[N], ans[N];
int col[N], sum[N];//col: 颜色桶   sum: 出现次数桶
inline void add(int x, int y){
    edge[++tot] = (node){y, head[x]};
    head[x] = tot;
}
inline void dfs(int x, int fa){
    siz[x] = 1;
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(y == fa) continue;
        dfs(y, x);
        siz[x] += siz[y];
        if(!son[x] || siz[son[x]] < siz[y])
            son[x] = y;
    }
}
inline void add(int x){
    col[c[x]]++, sum[col[c[x]]]++;// 经过 k 次时都会 + 1，所以下面直接 = sum [k] 即可
}
inline void del(int x){
    sum[col[c[x]]]--, col[c[x]]--;
}
inline void update(int x, int fa, int type){
    if(!type) add(x);
    else del(x);
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(y == fa) continue;
        update(y, x, type);
    }
}
inline void solve(int x, int fa){
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(y == fa || y == son[x]) continue;
        solve(y, x);
        update(y, x, 1);
    }
    if(son[x]) solve(son[x], x);
    add(x);
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(y == fa || y == son[x]) continue;
        update(y, x, 0);
    }
    for(auto y : g[x]) ans[y.id] = sum[y.k];// 统计答案，原因在上面注释中解释了
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    for(int i = 1; i < n; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    for(int i = 1; i <= m; i++){// 离线操作
        int u, k;
        scanf("%d%d", &u, &k);
        g[u].push_back(Query{i, k});
    }
    dfs(1, 0);
    solve(1, 0);
    for(int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
}
# 3. CF570D Tree Requests
显然有一个性质：若该串为回文串，那么出现次数为奇数的字母的个数小于等于 1。
所以我们维护一下深度的异或和即可。
emm…… 感觉说不清楚 QwQQwQ，还是直接看代码吧，感觉代码比较清楚些。
这道题可以用 bitsetbitset 稍微加速一下，其实没什么用，我只是为了熟练一下 bitsetbitset。
另外，要离线操作，得先把询问存下来。
第一种：
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }
    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 5e5 + 10;
typedef pair<int, int> P;
int n, m;
int fa[N];
char s[N];
vector <int> g[N];
vector <P> q[N];
int siz[N], son[N], dep[N];
inline void dfs(int x){
    siz[x] = 1, dep[x] = dep[fa[x]] + 1;
    for(auto y : g[x]){
        dfs(y), siz[x] += siz[y];
        if(siz[y] > siz[son[x]]) son[x] = y;
    }
}
int ans[N];
bitset <27> cnt[N];
inline void add(int x){
    cnt[dep[x]][s[x] - 'a'] = cnt[dep[x]][s[x] - 'a'] ^ 1;
}
inline void update(int x){
    add(x);
    for(auto y : g[x]) update(y);
}
inline void solve(int x, int typ){
    for(auto y : g[x])
        if(y != son[x]) solve(y, 0);
    if(son[x]) solve(son[x], 1);
    for(auto y : g[x])
        if(y != son[x]) update(y);
    add(x);
    for(auto y : q[x]) ans[y.fi] = cnt[y.se].count() <= 1;
    if(!typ) update(x);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), m = read();
    for(int i = 2; i <= n; ++i) g[fa[i] = read()].pb(i);
    scanf("%s", s + 1);
    for(int i = 1; i <= m; ++i){
        int a = read(), b = read();
        q[a].pb(P(i, b));
    }
    dfs(1), solve(1, 0);
    for(int i = 1; i <= m; ++i) puts(ans[i] ? "Yes" : "No");
    return 0;
}
第二种：
mark
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <bitset>
using namespace std;
const int N = 5e5 + 10;
int n, m;
char c[N];
struct node{
    int v, nxt;
}edge[N << 1];
int head[N], tot;
int siz[N], son[N], dep[N], ans[N];
bitset <27> sum[N];
int cnt[N][27];
struct Query{
    int id, d;
};
vector <Query> q[N];
inline void add(int x, int y){
    edge[++tot] = (node){y, head[x]};
    head[x] = tot;
}
inline void dfs(int x, int fa){
    siz[x] = 1;
    dep[x] = dep[fa] + 1;
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(y == fa) continue;
        dfs(y, x);
        siz[x] += siz[y];
        if(!son[x] || siz[son[x]] < siz[y])
            son[x] = y;
    }
}
inline void add(int x){// 这边一个函数就够了，因为是异或操作
    sum[dep[x]][c[x] - 'a'] = sum[dep[x]][c[x] - 'a'] ^ 1;
}
inline void update(int x, int fa){
    add(x);
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(y == fa) continue;
        update(y, x);
    }
}
inline void solve(int x, int fa){
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(y == fa || y == son[x]) continue;
        solve(y, x);
        update(y, x);
    }
    if(son[x]) solve(son[x], x);
    add(x);
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(y == fa || y == son[x]) continue;
        update(y, x);
    }
    for(auto y : q[x]) ans[y.id] = (sum[y.d].count() <= 1);// 更新答案
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 2, x; i <= n; i++){
        scanf("%d", &x);
        add(x, i), add(i, x);
    }
    scanf("%s", c + 1);
    for(int i = 1, a, b; i <= m; i++){
        scanf("%d%d", &a, &b);
        q[a].push_back((Query){i, b});
    }
    dfs(1, 0);
    solve(1, 0);
    for(int i = 1; i <= m; i++)
        puts(ans[i] ? "Yes" : "No");
    return 0;
}
# 4. CF208E Blood Cousins
这道题就有点意思了。
我们先把题目转化一下，变成查找 uu 结点，的第 kk 级儿子有多少个。
所以我们要倍增查一下祖先，然后 addadd 函数 ++++。
统计答案的时候是 cnt[dep[x]+k]cnt[dep[x] + k]，要把自己本身的深度也加上。
嗯，大概就这样。
看代码吧。
mark
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ri register int
using namespace std;
inline int read(){
    int x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x;
}
const int N = 1e5 + 10;
int n, m;
struct node{
    int v, nxt;
}edge[N << 1];
struct Query{
    int id, k;
};
vector <Query> q[N];
int head[N], tot;
int fa[N][18], cnt[N];
int siz[N], dep[N], son[N], ans[N];
inline void add(int x, int y){
    edge[++tot] = (node){y, head[x]};
    head[x] = tot;
}
inline void dfs(int x, int f){
    siz[x] = 1, dep[x] = dep[f] + 1;
    for(ri i = 1; i <= 18; i++)// 预处理倍增数组
        if(fa[fa[x][i - 1]][i - 1])
            fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for(ri i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(y == f) continue;
        dfs(y, x);
        siz[x] += siz[y];
        if(!son[x] || siz[son[x]] < siz[y])
            son[x] = y;
    }
}
inline int find_fa(int x, int k){// 倍增查找 k 级祖先
    for(ri i = 18; i >= 0; i--)
        if(k >= (1 << i))
            k -= (1 << i), x = fa[x][i];
    return x;
}
inline void add(int x){
    cnt[dep[x]]++;
}
inline void del(int x){
    cnt[dep[x]] = 0;
}
inline void update(int x, int type){
    if(!type) add(x);
    else del(x);
    for(ri i = head[x]; i; i = edge[i].nxt)
        update(edge[i].v, type);
}
// 这个 solve 有一点改动，主要是因为我之前那种写法挂了，调了好久都没调出来 QWQ
inline void solve(int x, int flag){//flag 标记重儿子还是轻儿子，= 1 是重儿子
    for(ri i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(y == son[x]) continue;
        solve(y, 0);// 处理轻儿子
    }
    if(son[x]) solve(son[x], 1);// 重儿子
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(y == son[x]) continue;
        update(y, 0);// 加入轻儿子
    }
    add(x);// 加入根
    for(auto y : q[x]) ans[y.id] = cnt[dep[x] + y.k];// 统计答案，这里是节点 x 的向下 k 级祖先，所以深度为 dep [x] + y.k
    if(!flag) update(x, 1);// 如果是轻儿子，就删除信息
}
int main(){
    n = read();
    for(ri i = 1; i <= n; i++){
        int x = read();
        fa[i][0] = x;
        add(x, i);
    }
    for(ri i = 1; i <= n; i++)
        if(!fa[i][0])// 注意这是个森林
            dfs(i, 0);
    m = read();
    for(ri i = 1; i <= m; i++){// 离线
        int u = read(), k = read();
        int p = find_fa(u, k);
        if(p) q[p].push_back((Query){i, k});// 记录询问
    }
    for(ri i = 1; i <= n; i++)
        if(!fa[i][0]) solve(i, 0);// 森林
    for(ri i = 1; i <= m; i++)
        printf("%d ", max(ans[i] - 1, 0));// 要减去查找的那个点
    puts("");
    return 0;
}
# 总结
这是一个暴力的算法，算法的难点在于找到题目中可以快速合并的性质。
找到之后，我们就可以通过把儿子的数据全都合并到重儿子上面这种方法快速求出我们想要的答案。
_EOF_\_EOF\_