Codeforces 741 D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

思路：

樹上啟發式合并

從根節點出發到每個位置的每個字符的奇偶性記為每個位置的狀態，每次統計一下每個狀態的最大深度

為了保證鏈經過當前節點u，我們先計算每個子樹的答案，再更新子樹狀態對深度的貢獻。

代碼：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
//#define mp make_pair
#define pb push_back
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdi pair<double, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head

inline int read() {int a = 1, b = 0;char ch = getchar();while(ch < '0' || ch > '9') {if(ch == '-') a = -1;ch = getchar();}while('0' <= ch && ch <= '9') {b = b*10 + ch-'0';ch = getchar();}return a*b;
}
const int N = 5e5 + 5, M = 5e6 + 5;
const int INF = 1e8;
vector<pii> g[N];
int n, p, dp[N], sz[N], son[N], deep[N], st[N], mx[M];
char c[2];
void get_son(int u, int o) {sz[u] = 1;deep[u] = deep[o] + 1;for (int i = 0; i < g[u].size(); ++i) {int v = g[u][i].fi;int w = g[u][i].se;st[v] = st[u] ^ (1<<w);get_son(v, u);if(sz[v] > sz[son[u]]) son[u] = v;sz[u] += sz[v];}
}
void CAL(int p, int u) {if(mx[st[u]] >= 0) dp[p] = max(dp[p], mx[st[u]]+deep[u]-2*deep[p]);for (int i = 0; i < 22; ++i) {if(mx[st[u]^(1<<i)] >= 0) dp[p] = max(dp[p], mx[st[u]^(1<<i)]+ deep[u]-2*deep[p]);}for (int i = 0; i < g[u].size(); ++i) {int v = g[u][i].fi;CAL(p, v);}
}
void ADD(int u) {mx[st[u]] = max(mx[st[u]], deep[u]);for (int i = 0; i < g[u].size(); ++i) {int v = g[u][i].fi;ADD(v);}
}
void DELETE(int u) {if(mx[st[u]] >= 0) mx[st[u]] = -INF;for (int i = 0; i < g[u].size(); ++i) {int v = g[u][i].fi;DELETE(v);}
}
void dfs(int u) {for (int i = 0; i < g[u].size(); ++i) {int v = g[u][i].fi;if(v != son[u]) {dfs(v);DELETE(v);}}if(son[u]) dfs(son[u]);if(mx[st[u]] >= 0) dp[u] = mx[st[u]] - deep[u];for (int i = 0; i < 22; ++i) {if(mx[st[u]^(1<<i)] >= 0) dp[u] = max(dp[u], mx[st[u]^(1<<i)] - deep[u]);}mx[st[u]] = max(mx[st[u]], deep[u]);for (int i = 0; i < g[u].size(); ++i) {int v = g[u][i].fi;if(v != son[u]) {CAL(u, v);ADD(v);}}for (int i = 0; i < g[u].size(); ++i) {int v = g[u][i].fi;dp[u] = max(dp[u], dp[v]);}
}
int main() {n = read();for (int i = 2; i <= n; ++i) {p = read();scanf("%s", c);g[p].pb({i, c[0]-'a'});}get_son(1, 0);for (int i = 0; i < M; ++i) mx[i] = -INF;dfs(1);for (int i = 1; i <= n; ++i) printf("%d%c", dp[i], " \n"[i==n]);return 0;
}

?