D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
http://codeforces.com/problemset/problem/741/D
题意：
一棵根为1 的树，每条边上有一个字符（a-v共22种）。 求每个子树内的最长的路径，使得路径上的边按照一定顺序排列后是回文串。
分析：
dsu on tree。询问子树信息。
首先将这22个字符，转化为二进制。a=1,b=10,c=100...如果一条路径可以是回文串，那么要求路径的异或和最多有一个1。所以记录下从根到每个点的异或和，那么一条路径的异或和就是dis[u]^dis[v]，lca上面的异或后消失了。
之后维护每个子树内异或和为x的最大深度是多少。记为f。
更新答案：按照点分治的思想，先更新不经过根的，然后求出经过根的（更新分成两步，第一步更新答案，第二步更新f数组。防止更新了在子树内部的）。
代码：
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<cctype> 7 #include<set> 8 #include<vector> 9 #include<queue> 10 #include<map> 11 using namespace std; 12 typedef long long LL; 13 14 inline int read() { 15 int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; 16 for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f; 17 } 18 19 const int N = 500005; 20 21 int head[N], nxt[N], to[N], len[N], En; 22 int fa[N], siz[N], son[N], dis[N], deth[N], ans[N]; 23 int f[(1 << 22) + 5]; 24 int Mx, D; 25 26 void add_edge(int u,int v,int w) { 27 ++En; to[En] = v; len[En] = w; nxt[En] = head[u]; head[u] = En; 28 } 29 30 void dfs(int u) { 31 siz[u] = 1; 32 deth[u] = deth[fa[u]] + 1; 33 for (int i=head[u]; i; i=nxt[i]) { 34 int v = to[i]; 35 fa[v] = u; 36 dis[v] = dis[u] ^ (1 << len[i]); 37 dfs(v); 38 siz[u] += siz[v]; 39 if (!son[u] || siz[son[u]] < siz[v]) son[u] = v; 40 } 41 } 42 43 void add(int u) { 44 if (f[dis[u]]) Mx = max(Mx, deth[u] + f[dis[u]] - D); // 异或后为0 45 for (int i=0; i<22; ++i) // 异或后有一个1 46 if (f[(1 << i) ^ dis[u]]) Mx = max(Mx, deth[u] + f[(1 << i) ^ dis[u]] - D); 47 } 48 void Calc(int u) { // 计算答案 49 add(u); 50 for (int i=head[u]; i; i=nxt[i]) Calc(to[i]); 51 } 52 void upd(int u) { 53 f[dis[u]] = max(deth[u], f[dis[u]]); 54 } 55 void update(int u) { // 更新f数组 56 upd(u); 57 for (int i=head[u]; i; i=nxt[i]) update(to[i]); 58 } 59 void Clear(int u) { 60 f[dis[u]] = 0; 61 for (int i=head[u]; i; i=nxt[i]) Clear(to[i]); 62 } 63 64 void solve(int u,bool c) { 65 for (int i=head[u]; i; i=nxt[i]) 66 if (to[i] != son[u]) solve(to[i], 0); 67 if (son[u]) solve(son[u], 1); 68 69 D = deth[u] * 2; 70 for (int i=head[u]; i; i=nxt[i]) Mx = max(Mx, ans[to[i]]); //不经过根的 71 for (int i=head[u]; i; i=nxt[i]) 72 if (to[i] != son[u]) Calc(to[i]), update(to[i]); // update(u) !!！ 先更新答案，在更新f数组，（防止计算到在子树内部的路径） 73 add(u); upd(u); 74 ans[u] = Mx; 75 if (!c) Clear(u), Mx = 0; 76 } 77 78 int main() { 79 int n = read(); 80 char c[10]; 81 for (int i=2; i<=n; ++i) { 82 int u = read(); scanf("%s", c); 83 add_edge(u, i, c[0] - 'a'); 84 } 85 dfs(1); 86 solve(1, 1); 87 for (int i=1; i<=n; ++i) printf("%d ",ans[i]); 88 return 0; 89 }