思路:
对于一条链可以组成回文串,意味着最多只有一个奇数字母,比起我们记录路径各个字母的个数和,我们可以发现回文串实际上不在意真正的个数,只在意个数的奇偶。又我们发现字母只有20来个,可以使用状态压缩,那么我们只需要判断压缩后状态里1的个数是否为0或者1.
对于树上的链异或和,我们都可以用前缀异或和的思想,将x->y的异或和看成v[x]^v[fa[lca]]^v[y]^v[fa[lca]],v表示该点到根的异或和,可以发现就等于两个位置的异或和。
对于以x为根的子树里的链只有三种情况:
1.不经过根
2.链的一端是根
3.跨过根
容易知道,对于第1种情况我们可以看成x子树里的某个子树的情况3,所以我们只需要计算每个点的子树里的2,3情况即可。
假如我们遍历到第y个子树,前面已经遍历处理完x个子树。我们要处理y和前面x个子树的跨根贡献的话,我们不能先将y子树的值处理了,因为这可能导致结果是y和y子树里不经过根的链,
所以对于每次我们先calc掉x和y的链,再add掉y这个子树的内容。
代码:
#include<bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int N=5e5+10;
const int mod=1e9+7;
#define fi first
#define se second
int n,val[N];
vector<int> ve[N];
int son[N],siz[N];
int fac[30],mask[N],dep[N];
int ans[N],maxx,vis[(1<<25)];
int flag;
int rtdis;
void dfs1(int x,int f){
siz[x]=1;
dep[x]=dep[f]+1;
for(auto y:ve[x]){
if(y==f)
continue;
mask[y]^=mask[x];
dfs1(y,x);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]])
son[x]=y;
}
}
void calc(int u,int f){
if(vis[mask[u]]){
maxx=max(maxx,vis[mask[u]]+dep[u]-rtdis);
}
for(int i=0;i<=22;i++){
if(vis[mask[u]^fac[i]]){
maxx=max(maxx,vis[mask[u]^fac[i]]+dep[u]-rtdis);
}
}
for(auto v:ve[u]){
if(v==f||v==flag)
continue;
calc(v,u);
}
}
void add(int u,int f,int value){
if(value==1){
vis[mask[u]]=max(vis[mask[u]],dep[u]);
}
else{
vis[mask[u]]=0;
}
for(auto v:ve[u]){
if(v==f||v==flag)
continue;
add(v,u,value);
}
}
void dfs2(int u,int f,bool keep){
for(auto v:ve[u]){
if(v==f||v==son[u])
continue;
dfs2(v,u,0);
ans[u]=max(ans[u],ans[v]);//不经过根节点
}
if(son[u]){
dfs2(son[u],u,1);
flag=son[u];
ans[u]=max(ans[u],ans[son[u]]);//不经过根节点
}
rtdis=dep[u]*2;//根节点的dep两倍,方便下面for循环计算跨根的距离
for(auto v:ve[u]){//计算跨根距离,dis(u,v)=dep(u)+dep(v)-2dep(lca),lca就是现在的u
if(v==f||v==flag)
continue;
calc(v,u);//跨根计算和点分治一样,遍历了x个子树,现在是y子树,先不加y子树的贡献
add(v,u,1);//先计算y到前面x个子树的距离,算完再加上y子树的贡献,add
}
//以根为一端
if(vis[mask[u]]){//异或为0
maxx=max(maxx,vis[mask[u]]-dep[u]);
}
for(int i=0;i<=22;i++){//遍历异或和为2的幂
if(vis[mask[u]^fac[i]]){
maxx=max(maxx,vis[mask[u]^fac[i]]-dep[u]);
}
}
//前面的add都是从子节点进去的,没有跟新到当前节点
vis[mask[u]]=max(vis[mask[u]],dep[u]);//同理先不算当前节点的贡献,算完这种情况再add
flag=0; //flag清空是为了下面如果keep=0时把整个子树删掉(包括这颗子树的重儿子)
ans[u]=max(maxx,ans[u]);//三种情况都计算完了再更新答案
if(!keep){
add(u,f,-1);//add里没有重置maxx和rtdis
maxx=0;//答案已经存在ans【u】了,删除整个子树要重置maxx
//maxx不重置在回溯回去更新其他子树(不包括当前maxx链的子树)答案会可能取不到这个maxx
//rtdis=0;rtdis可重置可不重置,因为用前都重新赋值
}
}
void solve(){
cin>>n;
fac[0]=1;
for(int i=1;i<=23;i++)
fac[i]=fac[i-1]*2;
for(int i=2;i<=n;i++){
int a;
char b;
cin>>a>>b;
ve[a].push_back(i);
ve[i].push_back(a);
val[i]=fac[b-'a'];
mask[i]=fac[b-'a'];
}
dfs1(1,0);
dfs2(1,0,0);
for(int i=1;i<=n;i++)
cout<<ans[i]<<' ';
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}