物流企业网站建设特色,全屋设计装修效果图,简书wordpress主题,南京自助建站软件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
