CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths 树上启发式合并（DSU ON TREE）

题目描述

一棵根为\(1\) 的树，每条边上有一个字符（\(a-v\)共\(22\)种）。一条简单路径被称为\(Dokhtar-kosh\)当且仅当路径上的字符经过重新排序后可以变成一个回文串。求每个子树中最长的\(Dokhtar-kosh\)路径的长度。

输入输出样例

输入 #1

4

1 s

2 a

3 s

输出 #1

3 1 1 0

输入 #2

5

1 a

2 h

1 a

4 h

输出 #2

4 1 0 1 0

分析

一道树上启发式合并的好题

首先，我们来考虑什么样的情况下路径上的字符重新排列之后能够形成回文串

很显然，只有当路径上每种字母的数量都为偶数个或者有且仅有一种字母的数量是奇数个时才满足条件

这两种情况分别对应奇回文串和偶回文串

然后我们会发现字母只有 \(22\) 种，因此字母的状态可以状压

而题目的要求仅仅是判断奇偶性，因此我们用 \(0\) 表示偶数，用 \(1\) 表示奇数

那么满足要求的状态只有 \(0\) 和 \(2^i\)

那么我们就可以存储每一种状态所对应的节点的最大深度

转移时，当前的结点的 \(dp\) 值会由三种情况转移过来

1、在儿子节点的 \(dp\) 值中取 \(max\)

2、从儿子节点中选择一条链和当前的节点组成一条新的链

3、从两个不同的儿子节点中选择两条链和当前的节点组成一条新的链

为了避免出现自己更新自己的情况，我们要计算完一个儿子节点后再计算另一个儿子节点

代码

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define rg register

const int maxn=4e6+5;

int h[maxn],tot=1,n;

struct asd{

	int to,nxt,val;

}b[maxn];

void ad(int aa,int bb,int cc){

	b[tot].to=bb;

	b[tot].nxt=h[aa];

	b[tot].val=cc;

	h[aa]=tot++;

}

int siz[maxn],son[maxn],dep[maxn];

int f[maxn],dp[maxn],orz,ans[maxn<<2],yh[maxn],mmax,haha;

void dfs1(int now,int fa){

	siz[now]=1;

	dep[now]=dep[fa]+1;

	f[now]=fa;

	for(rg int i=h[now];i!=-1;i=b[i].nxt){

		rg int u=b[i].to;

		if(u==fa) continue;

		yh[u]=yh[now]^(1<<b[i].val);

		dfs1(u,now);

		siz[now]+=siz[u];

		if(son[now]==0 || siz[u]>siz[son[now]]){

			son[now]=u;

		}

	}

}

void js(int now){

	if(ans[yh[now]]) mmax=std::max(mmax,ans[yh[now]]+dep[now]-haha);

	for(int i=0;i<=22;i++){

		if(ans[yh[now]^(1<<i)])mmax=std::max(mmax,ans[yh[now]^(1<<i)]+dep[now]-haha);

		//只有当ans值存在的时候才能转移

	}

	for(rg int i=h[now];i!=-1;i=b[i].nxt){

		rg int u=b[i].to;

		if(u==f[now] || u==orz) continue;

		js(u);

	}

}

//计算子树对父亲节点的贡献

void add(int now,int op){

	if(op==1){

		ans[yh[now]]=std::max(ans[yh[now]],dep[now]);

	} else {

		ans[yh[now]]=0;

	}

	for(rg int i=h[now];i!=-1;i=b[i].nxt){

		rg int u=b[i].to;

		if(u==f[now] || u==orz) continue;

		add(u,op);

	}

}

//加入或删除子树贡献

void dfs2(int now,int fa,int op){

	for(rg int i=h[now];i!=-1;i=b[i].nxt){

		rg int u=b[i].to;

		if(u==f[now] || u==son[now]) continue;

		dfs2(u,now,0);

		dp[now]=std::max(dp[now],dp[u]);

	}

	if(son[now]){

		dfs2(son[now],now,1);

		orz=son[now];

		dp[now]=std::max(dp[now],dp[son[now]]);

	}

	//先递归轻儿子，再递归重儿子

	haha=dep[now]*2;

	for(rg int i=h[now];i!=-1;i=b[i].nxt){

		rg int u=b[i].to;

		if(u==orz || u==fa) continue;

		js(u);

		add(u,1);

	}

	//计算完一个子树的贡献再加入另一个子树的贡献

	mmax=std::max(mmax,ans[yh[now]]-dep[now]);

	for(rg int i=0;i<=22;i++){

		mmax=std::max(mmax,ans[yh[now]^(1<<i)]-dep[now]);

	}

	//即使ans值不存在，也不会更新

	ans[yh[now]]=std::max(ans[yh[now]],dep[now]);

	//从子树中选择一条链和当前节点连起来

	orz=0;

	dp[now]=std::max(mmax,dp[now]);

	if(op==0){

		add(now,-1);

		//清除轻儿子贡献

		mmax=haha=0;

	}

}

int main(){

	memset(h,-1,sizeof(h));

	scanf("%d",&n);

	rg int aa;

	char bb;

	for(rg int i=2;i<=n;i++){

		scanf("%d %c",&aa,&bb);

		ad(aa,i,bb-'a');

		ad(i,aa,bb-'a');

	}

	dfs1(1,0);

	dfs2(1,0,0);

	for(int i=1;i<=n;i++){

		printf("%d ",dp[i]);

	}

	printf("\n");

	return 0;

}

巴特西