题目大意：给一棵以1为根的树，每条边有一个字母，字母范围在a到v。一条合法路径表示这条路径上的字母重新排列后可以组成一个回文串。问每棵子树中合法路径最长是多少。
明显形成回文串的条件就是最多一个字母出现奇数次，其他全为偶数次。
然后这个字母范围只给到了v，也就是第22个字母，就可以考虑压位。也就是说，设当前答案的状态为$S$，那么$S$只能表示为$2^k$或$0$的形式。
考虑暴力：直接递归遍历每棵子树，看其左边和右边的合法路径，然后组合一下，算个最大值。这样是$O(n^2)$的。
然后就要引入一个神奇的优化算法：树上启发式合并。
啥意思呢？因为深层的子树的信息是可以不用重复计算的，可以直接往上搞，但是有一部分信息会需要更新。我们就考虑优化这一部分的更新。
考虑分治：我们是对每棵子树的信息进行一个维护和更新，树分治的话也是个不错的解决方案。不过dsu on tree可以替代解决很多问题。
考虑轻重链剖分，轻链的信息可以直接往最近的重儿子上更新，这一部分是线性的更新；然后重儿子再往上爬，每上升一个重儿子的复杂度是$O(1)$的。
然后总的复杂度是多少呢？由于是轻重链剖分，回想一下树链剖分，在树上更新区间的时候复杂度大概是$logn$左右，那么在这里也是一样的，总的复杂度也是$O(nlogn)$。
是不是很神奇......
下面这个代码还算跑得贼慢的......跑了2s
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
const int N=500050;
const int inf=0x3f3f3f3f;
inline int idx(char c){return c-'a';}
inline int tr(char c){return 1<<idx(c);}
int n,ans[N];
struct edge
{
int v;
int nxt;
int w;
}e[N];
int head[N],ecnt;
inline void ad(int u,int v,int w)
{
e[++ecnt].v=v;e[ecnt].nxt=head[u];head[u]=ecnt;
e[ecnt].w=w;
}
int dep[N],son[N],siz[N],xors[N],p[(1<<22)+5];
void dfs(int u)
{
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
dep[v]=dep[u]+1;
xors[v]^=xors[u];
dfs(v);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v])son[u]=v;
}
}
void upd(int now,int u)
{
ans[now]=max(ans[now],dep[u]+p[xors[u]]);
for(int i=0;i<22;++i)
{
ans[now]=max(ans[now],dep[u]+p[(1<<i)^xors[u]]);
}
for(int i=head[u];i;i=e[i].nxt)
{
upd(now,e[i].v);
}
}
void Undo(int u)
{
p[xors[u]]=-inf;
for(int i=head[u];i;i=e[i].nxt)Undo(e[i].v);
}
void Insert(int u)
{
p[xors[u]]=max(p[xors[u]],dep[u]);
for(int i=head[u];i;i=e[i].nxt)Insert(e[i].v);
}
void Dfs(int u)
{
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v!=son[u])
{
Dfs(v);
Undo(v);
}
}
if(son[u])Dfs(son[u]);
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v!=son[u])
{
upd(u,v);
Insert(v);
}
}
p[xors[u]]=max(p[xors[u]],dep[u]);
ans[u]=max(ans[u],dep[u]+p[xors[u]]);
for(int i=0;i<22;++i)
{
ans[u]=max(ans[u],dep[u]+p[(1<<i)^xors[u]]);
}
ans[u]=ans[u]-(dep[u]<<1);
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
ans[u]=max(ans[u],ans[v]);
}
}
int main()
{
scanf(
for(int i=0;i<=(1<<22);++i)p[i]=-inf;
ecnt=1;
for(int i=2;i<=n;++i)
{
int pp;char c;
cin>>pp>>c;
ad(pp,i,tr(c));
xors[i]=tr(c);
}
dfs(1);
Dfs(1);
for(int i=1;i<=n;++i)
printf(
return 0;
}
Comments NOTHING