CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths (dsu on tree) 题解

先说一下dsu算法。

例题：子树众数问题。

给出一棵树，每个点有点权，求每个子树中出现次数最多的数的出现次数。

树的节点数为n，(n leq 500000)

这个数据范围，(O(n sqrt n))直接莫队会超时。

考虑一种暴力做法：

开一个全局数组，记录每中数的出现次数。

依次对每个点，用dfs遍历它的子树，并记录每种数的出现次数。

遍历结束后，找到众数，记录结果，并清空这个数组，进行下一次遍历。

可以发现，在最坏情况（例如一条链），算法的时间复杂度是(O(n^2))的。

但是，对于一条链，只要从下至上扫描一遍，就能得出解。

而这样就相当于子树统计后的数组没有清空，而是留给了父节点。

所以，考虑这种优化：

（除根以外）每个结点都有它的父节点，所以，其实无须清空数组，直接留给父节点就行。

但是，如果一个节点的所有子结点都不删除，会很费空间，而且，我们还要将这些子树信息都合并，而合并也是(O(n))的，每个节点都要合并，所以总复杂度还是(O(n^2))的。

所以，对于每个节点，只能保留一个子结点，其余的还要清空。

为了使效率最高，应该保存子结点数量最多的儿子（即重儿子）。

优化后的时间复杂度：

每个节点，只有在祖先结点到父亲的是轻边时，才会被计算，所以每个最多会算(O(log n))次。总时间复杂度就优化到了(O(n log n))。

要自底向上遍历每个节点。对于每个节点，先遍历轻儿子，再遍历重儿子，最后计算它自己。

如果它到父亲的是轻边，就清空数组，否则不清空。

对于本题：

给一棵树，边上有一个字母（只有a到v共22个）。一条简单路径被称为Dokhtar-kosh当且仅当路径上的字符经过重新排序后可以变成一个回文串。

求每个子树中最长的Dokhtar-kosh路径的长度。

可以枚举每个点，然后求答案。

枚举每个点的子节点，依次将状压值放入数组求解。

注意卡常。

代码：

#include <stdio.h>
#define re register
#pragma GCC optimize("O3")
int fr[500001],ne[500001];
int v[500001],w[500001],bs=0;
int zd[4194304],zh[500001];
int jg[500001],sd[500001];
int son[500001];
int st[500001],tp=0;
bool so[500001];
void addb(int a,int b,int c)
{
	v[bs]=b;
	w[bs]=c;
	ne[bs]=fr[a];
	fr[a]=bs;
	bs+=1;
}
 #define max(x,y) (x)>(y)?(x):(y)
int dfs1(int u,int s)
{
	sd[u]=s;
	son[u]=-1;
	int ma=-1,rt=1;
	for(re int i=fr[u];i!=-1;i=ne[i])
	{
		int t=dfs1(v[i],s+1);
		rt+=t;
		if(t>ma)
		{
			ma=t;
			son[u]=v[i];
		}
	}
	if(son[u]!=-1)
		so[son[u]]=true;
	return rt;
}
void dfs2(int u,int z)
{
	zh[u]=z;
	for(re int i=fr[u];i!=-1;i=ne[i])
		dfs2(v[i],z^(1<<w[i]));
}
void  solve(re int u,re int wz)
{
	st[tp++]=u;
	if(zd[zh[u]]!=-1)
		jg[wz]=max(jg[wz],zd[zh[u]]+sd[u]);
	for(int i=0;i<22;i++)
	{
		if(zd[zh[u]^(1<<i)]!=-1)
			jg[wz]=max(jg[wz],zd[zh[u]^(1<<i)]+sd[u]);
	}
	for(re int i=fr[u];i!=-1;i=ne[i])
		solve(v[i],wz);
}
void clean(re int u)
{
	zd[zh[u]]=-1;
	for(re int i=fr[u];i!=-1;i=ne[i])
		clean(v[i]);
}
void dfs3(re int u)
{
	for(re int i=fr[u];i!=-1;i=ne[i])
	{
		if(v[i]!=son[u])
			dfs3(v[i]);
	}
	if(son[u]!=-1)
		dfs3(son[u]);
	for(re int i=fr[u];i!=-1;i=ne[i])
	{
		if(v[i]==son[u])
			continue;
		tp=0;
		solve(v[i],u);
		for(re int j=0;j<tp;j++)
			zd[zh[st[j]]]=max(zd[zh[st[j]]],sd[st[j]]);
	}
	if(zd[zh[u]]!=-1)
		jg[u]=max(jg[u],zd[zh[u]]+sd[u]);
	for(int i=0;i<22;i++)
	{
		if(zd[zh[u]^(1<<i)]!=-1)
			jg[u]=max(jg[u],zd[zh[u]^(1<<i)]+sd[u]);
	}
	if(!so[u])
		clean(u);
	else
		zd[zh[u]]=max(zd[zh[u]],sd[u]);
}
void dfs4(int u)
{
	jg[u]-=sd[u]*2;
	if(jg[u]<0)
		jg[u]=0;
	for(int i=fr[u];i!=-1;i=ne[i])
	{
		dfs4(v[i]);
		if(jg[v[i]]>jg[u])
			jg[u]=jg[v[i]];
	}
}
int main()
{	
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		fr[i]=-1;
	for(int i=2;i<=n;i++)
	{
		int f;
		char ch[2];
		scanf("%d%s",&f,ch);
		addb(f,i,ch[0]-'a');
	}
	for(int i=0;i<4194304;i++)
		zd[i]=-1;
	dfs1(1,0);
	dfs2(1,0);
	dfs3(1);
	dfs4(1);
	for(int i=1;i<=n;i++)
		printf("%d ",jg[i]);
	return 0;
}

CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths (dsu on tree) 题解

相关推荐