前排感谢AgOH大佬 orz 【AgOHの算法胡扯】树上启发式合并（dsu on tree）_哔哩哔哩_bilibili

思想很简单：大的向小的上面合并，根据轻重链的性质可以证明时间复杂度缩减为O(nlogn)具体证明可自行搜索。

题目：[P9233 蓝桥杯 2023 省 A] 颜色平衡树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

理解AgOH大佬的讲的模板题，这道题就会简单不少，唯一难点是判断颜色平衡树：

我们设计三个数组： color[i],cnt[i],cntcnt[i],color[i]表示节点i的颜色，cnt[i]表示颜色i出现的次数，cntcnt[i]表示 颜色出现次数 i 的出现的次数。

对于以x为根的子树，如果 设 **c=cnt[color[x]] , f=cntcnt[c] 如果 c*fsize[x] 那么他就是颜色平衡树。**原因：假设存在一个颜色出现的次数不等于c，那么必然 cf < size[x]，这与cfsize[x]矛盾，所以假设不成立。

当然，我们看到颜色个数这种问题，自然而然会想起来莫队的模板题（[P1903 国家集训队] 数颜色 / 维护队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)），这题也可以用莫队解决，只是需要先dfs一遍进行线性化而已，还是上面一样的判断方法，判断的时间复杂度为O(1)，整体时间复杂度为O(n*根号n),可以通过本题。唯一需要注意一点的是，为了操作方便可能还要多存一个dfx表示时间戳x的原来的节点编号。

法一：启发式合并AC代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>

#define ll long long

using namespace std;

const int maxn=200000+10;
vector<int> graph[maxn];

int n,root=1;
int color[maxn],son[maxn],t[2][maxn],siz[maxn];
//t[0][x]表示颜色x出现了几次，t[1][x]表示次数x出现的次数。

int ans=0,flag;//MINN,MAXN维护的是颜色出现的次数

void add(int x)
{
    t[1][t[0][x]]--;
    t[0][x]++;
    t[1][t[0][x]]++;
}

void del(int x)
{
    t[1][t[0][x]]--;
    t[0][x]--;
    t[1][t[0][x]]++;
}

void add_k(int now)
{
    add(color[now]);

    for(const auto&it : graph[now])
        if(it!=flag)add_k(it);
}


void del_k(int now)
{
    del(color[now]);

    for(const auto&it : graph[now])
        if(it!=flag)del_k(it);
}

void dfs(int now)
{
    int maxsize=-1;
    siz[now]=1;

    for(const auto&it : graph[now])
    {
        dfs(it);
        siz[now]+=siz[it];
        if(siz[it]>maxsize)
        {
            maxsize=siz[it];
            son[now]=it;
        }
    }
}


void dfs(int now,bool keep)
{
    for(const auto& it : graph[now])
        if(it != son[now])
            dfs(it,false);
    
    if(son[now]!=0)
    {
        dfs(son[now],true);
        flag=son[now];
    }

    add_k(now);
    flag=0;
    
    //这句话的含义是：color[now]出现的频次*这个频次的频次 ==  siz[now]，
    //则说明颜色出现最多的次数和颜色出现最小的次数相等。
    //原因是：如果存在一个颜色，其出现的频次不等于color[now]出现的频次，
    //那么，这个算式是小于size[now]的。
    if(t[0][color[now]]*t[1][t[0][color[now]]]==siz[now])
        ++ans;

    if(keep==false)
    {
        del_k(now);
    }
}

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

#ifdef LOCAL
    clock_t c1 = clock();
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif

//-------------------------------------------------

    cin>>n;

    for(int i=1,f;i<=n;++i)
    {
        cin>>color[i]>>f;
        graph[f].push_back(i);
    }

    dfs(root);
    dfs(root,true);

    cout << ans << endl;
//-------------------------------------------------

#ifdef LOCAL
    cout << "Time Used:\n" << clock() - c1 << " ms" << endl;
#endif

    //system("pause");
    return 0;
}

点击并拖拽以移动

法二：莫队AC代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>

#define ll long long

using namespace std;
 
const int maxn=200000+10;
vector<int> graph[maxn];

int n,root=1,tim=0,block;
int color[maxn],siz[maxn],dfn[maxn],dfx[maxn];
int cnt[maxn],cntcnt[maxn];

struct QUERY{
    int l,r;
    bool operator<(const QUERY& other)const{
        if(l/block==other.l/block)return r<other.r;
        return l<other.l;
    }
}query[maxn];

void dfs(int now)
{
    siz[now]=1;
    dfn[now]=++tim;
    dfx[tim]=now;

    for(const auto&it : graph[now])
    {
        dfs(it);
        siz[now]+=siz[it];
    }
}

void add(int x,int k)
{
    cntcnt[cnt[x]]--;
    cnt[x]+=k;
    cntcnt[cnt[x]]++;
}

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

#ifdef LOCAL
    clock_t c1 = clock();
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif

//-------------------------------------------------

    cin>>n;

    block=sqrt(n);

    for(int i=1,y;i<=n;++i)
    {
        cin>>color[i]>>y;
        graph[y].push_back(i);
    }

    dfs(root);

    for(int i=1;i<=n;++i)
        query[i]={dfn[i],dfn[i]+siz[i]-1};

    sort(query+1,query+1+n);

    int ans=0,l=1,r=1;
    add(color[dfn[1]],1);

    for(int i=1,c,f;i<=n;++i)
    {
        while(l<query[i].l)add(color[dfx[l++]],-1);
        while(l>query[i].l)add(color[dfx[--l]],1);
        while(r<query[i].r)add(color[dfx[++r]],1);
        while(r>query[i].r)add(color[dfx[r--]],-1);

        c=cnt[color[dfx[query[i].l]]],f=cntcnt[c];

        if(c*f==query[i].r-query[i].l+1)
            ++ans;
    }

    cout<<ans;
//-------------------------------------------------

#ifdef LOCAL
    cout << "\nTime Used: \n" << clock() - c1 << " ms" << endl;
#endif

    //system("pause");
    return 0;
}

点击并拖拽以移动