D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths (cf741D)

D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths (cf741D)

tag： dsu on tree，dp

题目链接

题意：

给你一棵树，每一条边的权值是'a' 到'v' 的字母，求在每一个点的子树上找一条的简单路径，使该路径包含的字符排序后成为回文串，输出长度即可。

做法：

字母'a'到'v'一共22个字母，摆明了要状压，每一位用来表示某字母的奇偶性，要满足排序后形成回文串，那么至多出现一个1
我们用dis[u]描述从根节点走到1走u的字母情况，dep[u]表示深度,f[dis[u]]表示字母奇偶情况相同时的最大深度
对于u子树中的最长链，有二种可能

• 最长链不经过u而直接来自某颗儿子的子树中
• 最长链经过u

我们分析一下第二种可能

• 最长链的一端为u
  子树中任意节点x的dis[x]一定有经过根节点u，u之前的路径都是一样的，从u到节点x的的路径就是 dis[x]^dis[u]
• u在最长链之间，x,y分别属于u的不同儿子的子树
  那么从x出发经过u到达y的路径可表示为， dis[x] ^ dis[u] ^ dis[u] ^ dis[y] = dis[x]^dis[y]
  理解了这些就很好写了，我们将问题转化为子树问题，使用启发式合并求解。

写了两版，都有注释可供参考

代码：

#define fst std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout << std::fixed << std::setprecision(20)
#define le "\n"
#define ll long long 
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+50;
const int mod=998244353;
int sz[N],son[N],dp[N];
int st[N],id[N],dep[N],dis[N],ed[N]; //st、ed描述dfs序的区间，id计入按dfs序排序后的节点，dep表示深度，dis用来描述路径f[dis[u]]-dep[u]
int dfs_time;
int f[(1<<22)+5]; //字母数字范围a~v 22个字母
struct node{
    int v,c;
};
vector<node> g[N];
void predfs(int u,int fa){
    sz[u] = 1;
    st[u] = ++dfs_time;
    id[dfs_time] = u; //其实就是把节点按dfs序排序了
    for(auto e: g[u]){
        if(e.v==fa) continue;
        dep[e.v] = dep[u] + 1;
        dis[e.v] = dis[u]^(1<<e.c); //将经过的路径的权值状压
        predfs(e.v,u);
        sz[u] += sz[e.v];
        if(sz[e.v]>sz[son[u]]) son[u] = e.v;
    }
    ed[u] = dfs_time;
}

void dfs(int u,int fa,int op){
    for(auto e : g[u]){
        if(e.v==son[u]||e.v==fa) continue;
        dfs(e.v,u,0);
        dp[u] = max(dp[u],dp[e.v]); //先树形dp一波，最长链可能在子树当中
    }
    if(son[u]) dfs(son[u],u,1),dp[u]=max(dp[u],dp[son[u]]); 
    
    //接下来算经过u的最长链
    //链经过u和重儿子，因为现在只保留了重儿子的信息
    if(f[dis[u]]) dp[u]=max(dp[u],f[dis[u]]-dep[u]);
	for(int i=0;i<22;i++){
		if(f[dis[u]^(1<<i)]) dp[u]=max(dp[u],f[dis[u]^(1<<i)]-dep[u]);
    }
    f[dis[u]] = max(f[dis[u]],dep[u]);//更新最大深度

    for(auto e: g[u]){
        if(e.v==son[u]||e.v==fa) continue;
        for(int i = st[e.v];i<=ed[e.v];i++){ //遍历子树
            int x = id[i];//当前节点
            if(f[dis[x]]) dp[u] = max(dp[u],f[dis[x]]+dep[x]-2*dep[u]);
			for(int k=0;k<22;k++){
				if(f[dis[x]^(1<<k)]) dp[u] = max(dp[u],f[dis[x]^(1<<k)]+dep[x]-2*dep[u]);
            }
        }
        for(int i = st[e.v];i<=ed[e.v];i++) f[dis[id[i]]] = max(f[dis[id[i]]],dep[id[i]]);//将轻儿子和重儿子合并
    }
    if(!op) for(int i=st[u];i<=ed[u];i++) f[dis[id[i]]]=0; //清楚贡献
    //为什么可以直接清0，虽然我们f[]是多个状态的最大值，但是这些状态都被包括在子树中，所以大胆删就好
}

int main() {
    fst;
    int n,x; cin>>n;
    char c;
    for(int i=2;i<=n;i++){
        cin>>x>>c;
        g[i].push_back({x,c-'a'});
        g[x].push_back({i,c-'a'});
    }
    predfs(1,0);
    dfs(1,0,1);
    for(int i=1;i<=n;i++) cout<<dp[i]<<" ";
    return 0;
}

#define fst std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout << std::fixed << std::setprecision(20)
#define le "\n"
#define ll long long 
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+50;
const int mod=998244353;
int sz[N],son[N],dp[N];
int dep[N],dis[N]; //st、ed描述dfs序的区间，id计入按dfs序排序后的节点，dep表示深度，dis用来描述路径
int dfs_time;
int f[(1<<22)+5]; //字母数字范围a~v 22个字母
struct node{
    int v,c;
};
vector<node> g[N];
void predfs(int u,int fa){
    sz[u] = 1;
    for(auto e: g[u]){
        if(e.v==fa) continue;
        dep[e.v] = dep[u]+1;
        dis[e.v] = dis[u]^(1<<e.c); //将经过的路径的权值状压
        predfs(e.v,u);
        sz[u] += sz[e.v];
        if(sz[e.v]>sz[son[u]]) son[u] = e.v;
    }
}

void update(int u,int fa,int op){ //op为0删除，op为1取最大
    f[dis[u]] = op ? max(f[dis[u]],dep[u]) : 0;
    for(auto e: g[u]){
        if(e.v==fa) continue;
        update(e.v,u,op);
    }
}

void count(int u,int fa,int tf){

    if(f[dis[u]]) dp[tf] = max(dp[tf],f[dis[u]]+dep[u]-2*dep[tf]);
    for(int k=0;k<22;k++){
        if(f[dis[u]^(1<<k)]) dp[tf] = max(dp[tf],f[dis[u]^(1<<k)]+dep[u]-2*dep[tf]);
    }

    for(auto e: g[u]){
        if(e.v==fa||e.v==son[tf]) continue;
        count(e.v,u,tf);
        if(u==tf) update(e.v,u,1);
    }
}

void dfs(int u,int fa,int op){
    for(auto e : g[u]){
        if(e.v==son[u]||e.v==fa) continue;
        dfs(e.v,u,0);
        dp[u] = max(dp[u],dp[e.v]); //先树形dp一波，最长链可能在子树当中
    }
    if(son[u]) dfs(son[u],u,1),dp[u]=max(dp[u],dp[son[u]]); 
    if(f[dis[u]]) dp[u]=max(dp[u],f[dis[u]]-dep[u]);
	for(int i=0;i<22;i++){
		if(f[dis[u]^(1<<i)]) dp[u]=max(dp[u],f[dis[u]^(1<<i)]-dep[u]);
    }
    f[dis[u]] = max(f[dis[u]],dep[u]);//更新最大深度
    //u不为链的一端
    count(u,fa,u);
    if(!op)  update(u,fa,0);
    //为什么可以直接清0，虽然我们f[]是多个状态的最大值，但是这些状态都被包括在子树中，所以大胆删就好
}

int main() {
    fst;
    int n,x; cin>>n;
    char c;
    for(int i=2;i<=n;i++){
        cin>>x>>c;
        g[i].push_back({x,c-'a'});
        g[x].push_back({i,c-'a'});
    }
    predfs(1,0);
    dfs(1,0,1);
    for(int i=1;i<=n;i++) cout<<dp[i]<<" ";
    return 0;
}