树上启发加点分治思想

题目链接

思路：

        对于一条链可以组成回文串，意味着最多只有一个奇数字母，比起我们记录路径各个字母的个数和，我们可以发现回文串实际上不在意真正的个数，只在意个数的奇偶。又我们发现字母只有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 secondint 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;
}