# CF #458 E. Palindromes in a Tree

http://codeforces.com/contest/914/problem/E

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>

using namespace std;

const int N = 2e5;
vector<int> g[N];
bool used[N];
int sz[N];
int a[N];
long long ans[N];

void dfs2(int u, int p) {
sz[u] = 1;
for (int v : g[u]) if (v != p && !used[v]) {
dfs2(v, u);
sz[u] += sz[v];
}
}

int dfs3(int u, int p, int x) {
for (int v : g[u]) if (v != p && !used[v]) {
// if (sz[v] >= x / 2) {
if (sz[v] > x / 2) {
return dfs3(v, u, x);
}
}
return u;
}

long long mp[1 << 20];

void dfs4(int u, int p, int val) {
val ^= a[u];
mp[val]++;
for (int v : g[u]) if (v != p && !used[v]) {
dfs4(v, u, val);
}
}

void dfs5(int u, int p, int val) {
val ^= a[u];
mp[val]--;
for (int v : g[u]) if (v != p && !used[v]) {
dfs5(v, u, val);
}
}

long long dfs6(int u, int p, int val) {
val ^= a[u];
long long cnt = mp[val];
for (int i = 0; i < 20; i++) {
// (2^i) xor val
cnt += mp[(1 << i) ^ val];
}
for (int v : g[u]) if (v != p && !used[v]) {
cnt += dfs6(v, u, val);
}
ans[u] += cnt;
return cnt;
}

void dfs(int u) {
dfs2(u, -1);
u = dfs3(u, -1, sz[u]);
dfs4(u, -1, 0);
used[u] = true;

long long cen = mp[0];
for (int i = 0; i < 20; i++) {
cen += mp[1 << i];
}

for (int v : g[u]) if (!used[v]) {
dfs5(v, u, a[u]);
cen += dfs6(v, u, 0);
dfs4(v, u, a[u]);
}
cen /= 2;
ans[u] += cen;

dfs5(u, -1, 0);

for (int v : g[u]) if (!used[v]) {
dfs(v);
}
}

int main() {
int n;
cin >> n;

for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
u--;
v--;
g[u].push_back(v);
g[v].push_back(u);
}
string s;
cin >> s;
for (int i = 0; i < n; i++) {
a[i] = 1 << (s[i] - 'a');
}

dfs(0);

for (int i = 0; i < n; i++) {
printf("%lld ", ans[i] + 1);
}
}


% pgfmanual version 3.0.1a
\documentclass[dvipdfmx,margin=1cm]{standalone}

\usepackage{newtxtext}
\usepackage{newtxmath}
\usepackage{tikz}

\usetikzlibrary{scopes}
\usetikzlibrary{calc} % pgfmanual.pdf p.142
\usetikzlibrary{shapes.geometric}

\begin{document}

\begin{tikzpicture}[
]

\begin{scope}[local bounding box=scope1]
\node [foo] (a) at (0,0) {$c$};
\node [bar,shape border uses incircle,shape border rotate=180,minimum size=2cm] (A) at (0:3) {};
\node [bar,shape border uses incircle,shape border rotate=300,minimum size=2cm] (B) at (120:3) {};
\node [bar,shape border uses incircle,shape border rotate=420,minimum size=2cm] (C) at (240:3) {};

% See pgfmanual.pdf p.703
\draw (a) -- (A.apex);
\draw (a) -- (B.apex);
\draw (a) -- (C.apex);

\node [baz] (u) at (B.center) {$u$};
\node [baz] (v) at (C.center) {$v$};

\draw [-latex,draw=black!80,line width=0.1cm] (u) -- (B.apex) .. controls (120:0.5) and (240:0.5) .. (C.apex) -- (v);
\end{scope}

\begin{scope}[shift={($(scope1.east)-(scope1.west)+(3.5cm,0)$)},local bounding box=scope2]
\node [foo] (a) at (0,0) {$c$};
\node [bar,shape border uses incircle,shape border rotate=180,minimum size=2cm] (A) at (0:3) {};
\node [bar,shape border uses incircle,shape border rotate=300,minimum size=2cm] (B) at (120:3) {};
\node [bar,shape border uses incircle,shape border rotate=420,minimum size=2cm] (C) at (240:3) {};

\draw (a) -- (A.apex);
\draw (a) -- (B.apex);
\draw (a) -- (C.apex);

\node [baz] (u) at (B.center) {$u$};
\node [baz] (v) at (C.center) {$v$};

\draw [-latex,draw=black!80,line width=0.1cm] (u) -- (a);
\draw [-latex,draw=black!80,line width=0.1cm] (a) -- (v);
\end{scope}

% \draw (scope1.south west) rectangle (scope1.north east);
% \draw (scope2.south west) rectangle (scope2.north east);

% \node [draw,circle] at (scope1.east) {};
% \node [draw,circle] at (scope2.west) {};

\draw [-latex,line width=0.05cm] ($(scope1.east) + (0.5cm,0)$) -- node [auto] {Decompose} ($(scope2.west) + (-0.5cm,0)$);
\end{tikzpicture}

\end{document}


### 感想

shape border uses incircle が結構重要っぽくて、これがないと90°単位でしか回転できないらしい。