题目

题目描述

给出一棵$n$个点且以$1$号节点为根的有根树，每个节点$i$有一种颜色$c[i]$，有$m$次询问，每次询问给出一个节点$x$，求以$x$为根节点的子树内有多少种不同的颜色

数据范围

$1 \leq n, m, c[i] \leq 10^5$

题解

dsu on tree（树上启发式合并）

用途

树上启发式合并，用于求解节点的答案可以由子树合并而来的问题，询问必须离线

前置知识

轻重链剖分（树链剖分）

算法流程

以上述模板题为例

首先一遍Dfs处理出重儿子

然后从根节点开始，递归的处理每个节点（计算每个节点的答案）

在处理一个节点$u$时，我们先处理好他的轻儿子，每处理完一个轻儿子，删除轻儿子的影响；最后处理重儿子，保留重儿子的影响（通过一个全局变量），在把所有轻儿子的影响加上以得到$u$的答案

添加或删除轻儿子的影响都是暴力进行的，即Dfs一遍

说起来不好说，结合一下代码吧

代码

#include <iostream>
#include <cstdio>

const int z[2] = {-1, 1};

int n, m;
int c[112345];
struct Edge
{
    int from, to, next;
} edge[212345];
int tot, head[112345];
int sz[112345], son[112345], cnt[112345]; // son是重儿子编号， cnt记录每个颜色出现了几次
int res, ans[112345];

void Addedge(int u, int v)
{
    edge[++ tot] = (Edge){u, v, head[u]};

    head[u] = tot;
}

void Dfs1(int u, int fa) // 轻重链剖分， 求出重儿子
{
    sz[u] = 1;

    for(int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].to;

        if(v == fa) continue;

        Dfs1(v, u);
        sz[u] += sz[v];

        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}

void Bf(int u, int fa, int x) // 暴力添加或者消除一棵子树的影响
{
    cnt[c[u]] += z[x];
    if(cnt[c[u]] == x) res += z[x];

    for(int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].to;

        if(v == fa) continue;

        Bf(v, u, x);
    }
}

void Dfs2(int u, int fa, bool dlt) // 递归处理每个节点， dlt表示是否应该消除影响（是不是轻儿子）
{
    for(int i = head[u]; i; i = edge[i].next) // 先处理轻儿子（处理完消除了影响）
    {
        int v = edge[i].to;

        if(v == fa || v == son[u]) continue;

        Dfs2(v, u, true);
    }
    if(son[u]) Dfs2(son[u], u, false); // 处理重儿子（没有删除影响）

    for(int i = head[u]; i; i = edge[i].next) //暴力添加回轻儿子的影响
    {
        int v = edge[i].to;

        if(v == fa || v == son[u]) continue;

        Bf(v, u, 1);
    }

    if(! cnt[c[u]]) res ++;
    cnt[c[u]] ++;

    ans[u] = res;

    if(dlt) Bf(u, fa, 0); // 消除影响
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i < n; i ++)
    {
        int u, v;
        scanf("%d%d", &u, &v);

        Addedge(u, v);
        Addedge(v, u);
    }
    for(int i = 1; i <= n; i ++) scanf("%d", &c[i]);

    Dfs1(1, 0);
    Dfs2(1, 0, true);

    scanf("%d", &m);
    for(int i = 1; i <= m; i ++)
    {
        int x;
        scanf("%d", &x);

        printf("%d\n", ans[x]);
    }

    return 0;
}

时间复杂度

每个节点都被递归处理一次$O(n)$

树链剖分的性质：每个节点到根节点的路径上的轻边数量不会超过$\log n$。证明好证：从根节点到任何一个节点的路径上，如果是轻儿子，那么子树的$size$至少要减半，所以最多有$\log n$个轻儿子，也就是$\log n$条轻边

一个节点被暴力添加的次数，就是它的祖先中轻儿子的数量，也就是说每个点最多被暴力的添加$\log n$次，删除也是同理， $O(n \log n)$

总时间复杂度$O(n \log n)$

Zth's Blog

dsu on tree(树上启发式合并)

题目