[Codeforces741D]Arpa's letter-marked tree and Mehrdad's Dokhtar-kosh paths——dsu on tree

男娘i 2022-01-13 04:13 193阅读 0赞

## 题目链接： ##

[Codeforces741D][]

### 题目大意：给出一棵树，根为$1$，每条边有一个$a-v$的小写字母，求每个点子树中的一条最长的简单路径使得这条路径上的边上的字母重排后是一个回文串。 ###

显然如果一条路径上的字母重排后是回文串，那么最多有一个字母有奇数个。我们用$2^\{22\}$的一个二进制来记录有哪些字母有奇数个。剩下的只需要$dsu\\ on\\ tree$来求每个点的答案即可。对于每个点记录它到根的路径上的字母的二进制状态，显然位于一个点两个不同子树中的点的状态异或起来就是这两个点间路径的二进制状态。开一个桶存每种状态的最大深度然后在对于每个点求答案时依次遍历子树求出最大值即可。注意遍历轻儿子时要先用轻儿子子树中的点更新答案之后再将轻儿子子树中的点的信息加入桶中。

#include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    using namespace std;
    int cnt[5000000];
    int head[500010];
    int to[1000010];
    int nex[1000010];
    int size[500010];
    int son[500010];
    int val[500010];
    int dep[500010];
    int tot;
    int n;
    int x,y;
    char ch[2];
    int ans[500010];
    int tag[500010];
    void add(int x,int y)
    {
    	nex[++tot]=head[x];
    	head[x]=tot;
    	to[tot]=y;
    }
    void dfs(int x)
    {
    	size[x]=1;
    	for(int i=head[x];i;i=nex[i])
    	{
    		dep[to[i]]=dep[x]+1;
    		val[to[i]]^=val[x];
    		dfs(to[i]);
    		size[x]+=size[to[i]];
    		if(size[to[i]]>size[son[x]])
    		{
    			son[x]=to[i];
    		}
    	}
    }
    void calc(int x,int anc)
    {
    	ans[anc]=max(ans[anc],cnt[val[x]]+dep[x]-2*dep[anc]);
    	for(int i=0;i<22;i++)
    	{
    		ans[anc]=max(ans[anc],cnt[val[x]^(1<<i)]+dep[x]-2*dep[anc]);
    	}
    	for(int i=head[x];i;i=nex[i])
    	{
    		calc(to[i],anc);
    	}
    }
    void solve(int x,int opt)
    {
    	if(opt==1)
    	{
    		cnt[val[x]]=max(dep[x],cnt[val[x]]);
    	}
    	else
    	{
    		cnt[val[x]]=-1<<30;
    	}
    	for(int i=head[x];i;i=nex[i])
    	{
    		solve(to[i],opt);
    	}
    }
    void dsu_on_tree(int x,int opt)
    {
    	for(int i=head[x];i;i=nex[i])
    	{
    		if(to[i]!=son[x])
    		{
    			dsu_on_tree(to[i],0);
    			ans[x]=max(ans[x],ans[to[i]]);
    		}
    	}
    	if(son[x])
    	{
    		dsu_on_tree(son[x],1);
    		ans[x]=max(ans[x],ans[son[x]]);
    	}
    	cnt[val[x]]=max(cnt[val[x]],dep[x]);
    	ans[x]=max(ans[x],cnt[val[x]]-dep[x]);
    	for(int i=0;i<22;i++)
    	{
    		ans[x]=max(ans[x],cnt[val[x]^(1<<i)]-dep[x]);
    	}
    	for(int i=head[x];i;i=nex[i])
    	{
    		if(to[i]!=son[x])
    		{
    			calc(to[i],x);
    			solve(to[i],1);
    		}
    	}
    	if(!opt)
    	{
    		solve(x,-1);
    	}	
    }
    int main()
    {
    	scanf("%d",&n);
    	for(int i=2;i<=n;i++)
    	{
    		scanf("%d%s",&x,ch);
    		add(x,i);
    		val[i]=1<<(ch[0]-'a');
    	}
    	dfs(1);
    	for(int i=0;i<=(1<<22);i++)
    	{
    		cnt[i]=-1<<30;
    	}
    	dsu_on_tree(1,1);
    	for(int i=1;i<=n;i++)
    	{
    		printf("%d ",ans[i]);
    	}
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10645756.html

[Codeforces741D]: https://codeforces.com/contest/741/problem/D