简介: 一个CF上的选手发明的算法, 但也就只有一些大佬用…ˉ▽ˉ

非常建议先学习重轻链-树链剖分

https://www.acwing.com/file_system/file/content/whole/index/content/12510335/

还有善良的年轻人点个赞吧❤️

DSU on Tree 树上启发式合并

使用场景: 统计一颗树所有子树内节点的信息

算法原理:贪心

特征: 通常需要一个全局的桶

CF246E-模板题-引导题

暴力:

应该都能写出来吧 很简单的

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

const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int fa[N];
string name[N];
unordered_set<string> s;
int depth;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs1(int u, int p)
{
    fa[u] = p;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (j != p) dfs1(j, u);
    }
}

void dfs2(int u, int dep)
{
    if (dep > depth) return;

    if (dep == depth) s.insert(name[u]);

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (j != fa[u])
            dfs2(j, dep + 1);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    memset(h, -1, sizeof h);

    int p, root;
    string str;
    for (int i = 1; i <= n; i++)
    {
        cin >> str >> p;

        if (!p) root = i;

        add(p, i);

        name[i] = str;
    }

    dfs1(root, 0);

    int m;
    cin >> m;

    int u, k;
    while (m--)
    {
        cin >> u >> k;

        depth = k;

        dfs2(u, 0);

        cout << s.size() << '\n';

        s.clear();
    }


    return 0;
}

实现方法:

对于每个节点, 总是先统计”轻”子树, 并将桶清空, 最后统计”重”子树, 并将桶保留

实现步骤:

1. 统计子树大小, 将每个最大的子树对于的子节点设为”重儿子” son[u];

2. dfs遍历整棵树, 对于节点u, 先统计轻子树的信息,再统计重儿子对于子树的信息, 最后统计u为根的子树信息, 视情况清空桶;

3. 通常需要预处理将询问离线;

性质1: 一个点总是有1个重儿子, 除了叶子节点;

性质2: 一个点可能是父节点的重儿子, 但不一定再重链上;

性质3: 一个点至多往上走logn步就被合并到”重链”;

再回到刚才那道题 就-很-简单了

1. 用set做桶, 每一个深度开一个set统计字符串的不同种类数;

2. 离线, 将m次询问挂在每个点上

就变成了这样

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

typedef pair<int, int> PII;

const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int fa[N];
int s[N], ans[N];
int son[N];
vector<PII> g[N];
string name[N];
int depth[N];
set<string> S[N];
int heavy;
int n;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs1(int u, int p, int dep)
{
    s[u] = 1;

    depth[u] = dep;
    fa[u] = p;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (j != p)
        {
            dfs1(j, u, dep + 1);

            s[u] += s[j];

            if (s[son[u]] < s[j]) son[u] = j;
        }
    }
}

void get(int u)
{
    for (auto [id, k] : g[u])
        if (depth[u] + k > n + 1) ans[id] = 0;
        else ans[id] = S[depth[u] + k].size();
}

void update(int u, int v)
{
    if (v == 1) S[depth[u]].insert(name[u]);
    else S[depth[u]].clear();

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (j != heavy) update(j, v);
    }
}

void dfs2(int u, int k)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (j != son[u]) dfs2(j, 0);
    }

    if (son[u])
    {
        dfs2(son[u], 1);
        heavy = son[u];
    }

    update(u, 1);

    heavy = 0;

    get(u);

    if (!k) update(u, -1);

    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    memset(h, -1, sizeof h);

    int p;
    string str;
    for (int i = 1; i <= n; i++)
    {
        cin >> str >> p;

        add(p, i);

        name[i] = str;
    }

    int m;
    cin >> m;

    int u, k;
    for (int i = 0; i < m; i++)
    {
        cin >> u >> k;

        g[u].push_back({i, k});
    }

    dfs1(0, 0, 0);
    dfs2(0, 0);

    for (int i = 0; i < m; i++) cout << ans[i] << '\n';


    return 0;
}