高端网站建设 恩愉科技,重庆住建网站,电子商务网站开发报价,如何制作网站赚钱D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths 思路#xff1a; 树上启发式合并 从根节点出发到每个位置的每个字符的奇偶性记为每个位置的状态#xff0c;每次统计一下每个状态的最大深度 为了保证链经过当前节点u#xff0c;我们先计算每个子树的答案…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)
#includebits/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 rt1, l, m
#define rs rt1|1, m1, r
//#define mp make_pair
#define pb push_back
#define ULL unsigned LL
#define pll pairLL, LL
#define pli pairLL, int
#define pii pairint, int
#define piii pairpii, int
#define pdi pairdouble, int
#define pdd pairdouble, 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);
//headinline 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;
vectorpii 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] ^ (1w);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]^(1i)] 0) dp[p] max(dp[p], mx[st[u]^(1i)] 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]^(1i)] 0) dp[u] max(dp[u], mx[st[u]^(1i)] - 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[in]);return 0;
} 转载于:https://www.cnblogs.com/widsom/p/10773406.html
