思路

顏色平衡樹，即子樹中的節點顏色均勻分布。所以要確認一個子樹是否為顏色平衡樹，需要得到它的所有節點的顏色，也就是要深搜它所有的子樹。

這個想法就很標準的啟發式合并了，何為啟發式合并？簡單來說，就是需要對每一個樹進行搜索，在搜索的過程中必然會產生重復搜索的情況。如何減少重復搜索呢，那就是提前對每一個樹（父節點樹）的最大的那個子樹（最大即節點最多）進行記錄。提前是說提前到搜索這個最大的子樹時，當搜索完它的最大子樹時我們不刪除這個子樹上的信息，在搜索父結點樹的時候就可以直接用了，不需要再去重新搜索了。

很板子了，思路不明白的再去看看其他博客。

代碼

#include <bits/stdc++.h>
#define N 200010
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;int n,color[N],ans;
vector<int> ve[N]; 
unordered_map<int,int> cnt;int nums[N],son[N],nowson;
void dfs(int u,int fa){//求重兒子 nums[u]=1;son[u]=0;for(auto &v:ve[u]){if(v==fa) continue;dfs(v,u);nums[u]+=nums[v];if(nums[son[u]]<nums[v]) son[u]=v;}
}void calc(int u,int fa,int c){//計算 cnt[color[u]]+=c;if(cnt[color[u]]==0) cnt.erase(color[u]); for(auto &v:ve[u]){if(v==fa||v==nowson) continue;calc(v,u,c);}
}void answer(){int fg=1,pre=0;for(auto it:cnt){if(pre&&it.second!=pre) fg=0;pre=it.second;}ans+=fg; 
}void dsu(int u,int fa,int keep){//dfs深搜 for(auto &v:ve[u]){if(v==fa||v==son[u]) continue;//重兒子不搜 dsu(v,u,0);}if(son[u]){//若有重兒子，單獨搜 dsu(son[u],u,1);nowson=son[u];} calc(u,fa,1);//計算當前節點 nowson=0;answer();//判斷是否顏色平衡 if(!keep) calc(u,fa,-1);//非重兒子刪除記錄 
}int main(){IOScin>>n;for(int i=1;i<=n;i++){int f;cin>>color[i]>>f;if(f) ve[i].push_back(f),ve[f].push_back(i);}dfs(1,-1);dsu(1,-1,0);cout<<ans<<endl;return 0;
}