专栏文章

题解：P9233 [蓝桥杯 2023 省 A] 颜色平衡树

AA7F3jK9pR0xf_
P9233题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mip3wkr5
此快照首次捕获于
2025/12/03 05:45
3 个月前
此快照最后确认于
2025/12/03 05:45
3 个月前
查看原文

题目传送门

思路

先考虑暴力。显然对每颗子树做一遍 dfs 判定，如何判定？可以把 CiC_i 装到桶 αi\alpha_i 里，设 βi\beta_i 表示有多少个 αj\alpha_j 为 ii，typtyp 表示元素种类，sizisiz_i 表示以 ii 为根的子树的大小。显然我们只需判定 typ∣sizutyp|siz_u 且 βsizu/typ=typ\beta_{siz_u/typ}=typ 即可。上述的数组插入 / 删除一个数均能 O(1)O(1) 维护，时间复杂度 O(n2)O(n^2)。
使用 dsu on tree 优化。我们不期望重儿子的子树遍历多次，因为它的节点数最多，损耗的时间最大。于是我们可以把每次重儿子遍历后的状态都保存不动，然后遍历非重儿子的子树，储存计算完后再删掉。因为轻边边数为 log⁡n\log n 条，所以总复杂度为 O(nlog⁡n)O(n\log n)。

Code

以下设 a=Ca=C，b=αb=\alpha，c=βc=\beta。
CPP
#include <bits/stdc++.h>
using namespace std;
#define il inline
#define pb push_back
const int N = 2e5 + 10;
vector<int> g[N];
int a[N], b[N], c[N], typ, ans, n;
int dp[N], siz[N], son[N], dfn[N], rdfn[N], dfscnt;
il void add(int x)
{
	c[b[x]]--, c[++b[x]]++;
	if(b[x] == 1) typ++;
}
il void del(int x)
{
	c[b[x]]--, c[--b[x]]++;
	if(!b[x]) typ--; 
}
il void dfs1(int u)
{
	dfn[u] = dp[u] = ++dfscnt;
	rdfn[dfscnt] = u;
	siz[u] = 1;
	son[u] = -1;
	for(auto &v : g[u])
	{
		dfs1(v);
		if(son[u] == -1 || siz[v] > siz[son[u]])
			son[u] = v;
		siz[u] += siz[v];
		dp[u] = max(dp[u], dp[v]);
	}
}
il void dfs2(int u, bool tag)
{
	for(auto &v : g[u])
		if(v != son[u])
			dfs2(v, 0);
	if(son[u] != -1)
		dfs2(son[u], 1);
	for(auto &v : g[u])
	{
		if(v != son[u])
		{
			for(int i = dfn[v];i <= dp[v];++i)
				add(a[rdfn[i]]);
		}
	}
	add(a[u]);
	if(siz[u] % typ == 0 && c[siz[u] / typ] == typ)
		ans++;
	if(!tag)
	{
		for(int i = dfn[u];i <= dp[u];++i)
			del(a[rdfn[i]]);
	}
}
int main()
{
	cin >> n;
	for(int i = 1;i <= n;++i)
	{
		int x;
		scanf("%d%d", &a[i], &x);
		if(!x) continue;
		g[x].pb(i);
	}
	c[0] = n;
	dfs1(1);
	dfs2(1, 0);
	cout << ans;
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...