SRM 729 Med. FrogSquare

問題概要

$n \times n$ のグリッドが与えられる。スタート地点は \((s_x, s_y)\) でゴール地点は \((g_x, g_y)\) である。ユークリッド距離が $d$ 以上の点に移動できる。移動回数の最小値を求めよ。ただし到達不可能な場合は $-1$ を出力せよ。

誤解法

四隅だけ使えばよく,到達できるなら 3 手で行ける。

反例。4 手の例。四隅だけでは到達不可能。

解法

最初と最後以外は周上以外の点に移動する必要はない。周上の点の個数のオーダーは \(O(n)\) なので,単純な BFS でも計算量は \(O(n^2)\) となる。

class FrogSquare {
public:
  int minimalJumps(int n, int d, int sx, int sy, int tx, int ty) {
    vector<pair<int, int>> g;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (i == 0 || i == n - 1 || j == 0 || j == n - 1) {
          g.emplace_back(i, j);
        }
      }
    }
    g.emplace_back(tx, ty);
    queue<pair<int, int>> q;
    q.emplace(sx, sy);
    vector<vector<int>> dist(n, vector<int>(n, -1));
    dist[sx][sy] = 0;
    while (!q.empty()) {
      int x = q.front().first;
      int y = q.front().second;
      q.pop();
      for (auto p : g) {
        int xx = p.first;
        int yy = p.second;
        if ((xx - x) * (xx - x) + (yy - y) * (yy - y) >= d * d && dist[xx][yy] == -1) {
          dist[xx][yy] = dist[x][y] + 1;
          q.emplace(xx, yy);
        }
      }
    }
    return dist[tx][ty];
  }
};

\documentclass[margin=1cm]{standalone}
\usepackage{tikz,newtxtext,newtxmath}

\begin{document}

\begin{tikzpicture}[
  foo/.style={fill,circle,inner sep=0,minimum size=2mm},
]
\clip (-1,-1) rectangle (11,11);
\draw [help lines] (0,0) grid (10,10);

\node [foo] (z) at (8,8) {};
\node [foo] (a) at (0,0) {};
\node [foo] (b) at (10,5) {};
\node [foo] (c) at (0,10) {};
\node [foo] (d) at (8,2) {};

\draw (8,8) circle [radius=11cm];
\draw (0,0) circle [radius=11cm];
\draw (10,5) circle [radius=11cm];
\draw (0,10) circle [radius=11cm];

\draw [->,>=latex,thick] (z) -- (a);
\draw [->,>=latex,thick] (a) -- (b);
\draw [->,>=latex,thick] (b) -- (c);
\draw [->,>=latex,thick] (c) -- (d);

\end{tikzpicture}

\end{document}

感想

自分の部屋では med の反例を作れる人がいなかったので,もし反例が作れてたらかなり稼げた(残念)。四隅の反例はすぐに作れたんだけど,4 手の例を作るのに手間取った。

ランダムに生成した行列は高確率で正則

$\mathbb{F}_p ^{2 \times 2}$ の行列をランダムに生成すると、高確率で正則になる。

$\mathbb{F}_p ^{2 \times 2}$ のうち、正則なものは $(p^2-1)(p^2-p)$ 個ある(解析は付録に書いておく)。そのため、ランダムに生成した行列が正則になる確率は

\begin{equation}
\frac{(p^2-p)(p^2-1)}{p^4} = \left( 1-\frac{1}{p} \right) \left( 1 - \frac{1}{p^2} \right)
\end{equation}

である。$p=10^9+7$ だと $6.93\times 10^8$ 個生成してようやく、正則でない行列が生成される確率が 50% 以上となる。つまり、ランダムに生成しただけでは正則でない行列はまず生成されない。

この結果から分かることは、逆元が存在しないと機能しないアルゴリズムであっても、テストケースがランダムに作られていると意外と落ちないということ。テストケースが雑なコンテストだと、これが考慮されてないことが稀にあるので嘘解法のチャンスである。もちろん、落とそうと思えば簡単に落とせるので勧めはしない。

付録

定理:$\mathbb{F}_p ^{n \times n}$ の元のうち正則なものは $(p^n-1)(p^n-p) \cdots (p^n-p^{n-1})$ 個ある。

証明の方針:行列をベクトルを $n$ 個並べたものと考えて、線形独立を崩さないように上の行から決定していくことを考えると式が求まる。

証明:第 $i$ 行目のベクトルを $\mathbf{u}_i$ と置く。
$\mathbf{u}_1$ の候補は $\mathbf{0}$ 以外なら何でも良いので $p^n-1$ 通りある。$\mathbf{u}_2$ の候補は、$0 \mathbf{u}_1, \ldots (p-1) \mathbf{u}_1$ 以外なら何でも良いので $p^n-p$ 通りある。

$\mathbf{u}_1,\ldots,\mathbf{u}_k$ が定まっていたとする。このとき $\mathbf{u}_{k+1}$ を付け加えて線形独立であるためには、$\mathbf{u}_{k+1}$ が $\mathbf{u}_1, \ldots, \mathbf{u}_k$ が張る部分空間に属さなければ良い。つまり $p^n - p^k$ 通りある。(証明終わり)

感想

単なるスカラーであれば $1-1/p$ なので、 行列とスカラーで逆元を持つ確率はほとんど変わらない。

状態がループするゲームの解析(後退解析)

状態がループするゲームは、DAG ではないため動的計画法が使えない。代わりに 後退解析 というテクニックを用いる。

次のゲームを考えよう。n 頂点 m 辺の有向グラフが与えられる。最初、頂点 s に駒が置かれている。プレイヤーは駒を隣接頂点に動かすことができる。この操作を交互に行い、動かせなくなった人が負けである。両者が最適な行動を行ったとき、どちらが勝つか、それとも勝負が決まらないか判定せよ。

有限状態のゲームはこのゲームに還元できる(確定とか二人とか完全情報とかあるけど察して)ので、最も重要なゲームとも言える。簡単なグラフを例にとって、後退解析がどのように行われるのか説明しよう。

解析の基本は、

  • 負け状態に遷移できるなら、その頂点は勝ち
  • 勝ち状態にしか遷移できないなら、その頂点は負け

である。


f:id:pekempey:20180201175639p:plain
図1. 与えられたグラフ


f:id:pekempey:20180201175856p:plain
図2. 移動先がない頂点は負け


f:id:pekempey:20180201180202p:plain
図3. 負け状態に遷移できる頂点は勝ち



f:id:pekempey:20180201180455p:plain
図4. 勝ち状態にしか遷移できないので負け


f:id:pekempey:20180201180640p:plain
図5. 負け状態に遷移できるので勝ち

ここまでの解析は queue を使って(トポロジカルソートみたいな感じでやれば)いける。なお、決まらなかったノードは引き分け状態である。理由を簡単に説明する。まず、決まらなかったノードは勝ち状態か引き分け状態にしか遷移できないはずである。勝ちノードに遷移させた瞬間に負けが確定するので、引き分けノードに遷移するしかない。さらに、引き分けノードからは引き分けノードに必ず遷移できる(もしそうでないなら、勝ち状態か負け状態か判定できるはずである)。すると、引き分けノードから引き分けノードに移動するという操作が無限に行われることが分かる。

図のコード

ちょっと頂点間隔が狭かったかなぁ。spring layout で綺麗に作れれば楽だったんだけど微妙にずれたので手打ちした。

図1

\documentclass[margin=0.5cm]{standalone}
\usepackage{tikz,newtxtext,newtxmath}
\usetikzlibrary{graphs,graphdrawing,calc}
\usegdlibrary{trees,force,circular}
\begin{document}

\begin{tikzpicture}[
    nodes={draw,fill=white,circle,minimum size=0.65cm},
    foo/.style={-latex},
  ]
  \node (0) {};
  \node (1) at ($(0)+(60:1)$) {};
  \node (2) at ($(0)+(0:1)$) {};
  \node (3) at ($(1)+(0:1)$) {};
  \node (4) at ($(3)+(30:1)$) {};
  \node (5) at ($(3)+(-30:1)$) {};
  \node (6) at ($(4)+(90:1)$) {};
  \node (7) at ($(5)+(-90:1)$) {};
  \node (8) at ($(5)+(30:1)$) {};
  \node (9) at ($(7)+(-90:1)$) {};
  \node (10) at ($(9)+(-90:1)$) {};
  \node (11) at ($(9)+cos(30)*(1,0)$) {};

  \draw [foo] (0) -- (1);
  \draw [foo] (1) -- (2);
  \draw [foo] (2) -- (0);
  \draw [foo] (2) -- (9);
  \draw [foo] (3) -- (1);
  \draw [foo] (4) -- (3);
  \draw [foo] (5) -- (3);
  \draw [foo] (4) -- (6);
  \draw [foo] (5) -- (7);
  \draw [foo] (8) -- (4);
  \draw [foo] (8) -- (5);
  \draw [foo] (11) -- (8);
  \draw [foo] (9) -- (11);
  \draw [foo] (9) -- (10);
\end{tikzpicture}

\end{document}

図2

\documentclass[margin=0.5cm]{standalone}
\usepackage{tikz,newtxtext,newtxmath}
\usetikzlibrary{graphs,graphdrawing,calc}
\usegdlibrary{trees,force,circular}
\begin{document}

\begin{tikzpicture}[
    nodes={draw,fill=white,circle,minimum size=0.65cm},
    foo/.style={-latex},
    lose/.style={fill=blue!70,text=white},
  ]
  \node (0) {};
  \node (1) at ($(0)+(60:1)$) {};
  \node (2) at ($(0)+(0:1)$) {};
  \node (3) at ($(1)+(0:1)$) {};
  \node (4) at ($(3)+(30:1)$) {};
  \node (5) at ($(3)+(-30:1)$) {};
  \node[lose] (6) at ($(4)+(90:1)$) {L};
  \node[lose] (7) at ($(5)+(-90:1)$) {L};
  \node (8) at ($(5)+(30:1)$) {};
  \node (9) at ($(7)+(-90:1)$) {};
  \node[lose] (10) at ($(9)+(-90:1)$) {L};
  \node (11) at ($(9)+cos(30)*(1,0)$) {};

  \draw [foo] (0) -- (1);
  \draw [foo] (1) -- (2);
  \draw [foo] (2) -- (0);
  \draw [foo] (2) -- (9);
  \draw [foo] (3) -- (1);
  \draw [foo] (4) -- (3);
  \draw [foo] (5) -- (3);
  \draw [foo] (4) -- (6);
  \draw [foo] (5) -- (7);
  \draw [foo] (8) -- (4);
  \draw [foo] (8) -- (5);
  \draw [foo] (11) -- (8);
  \draw [foo] (9) -- (11);
  \draw [foo] (9) -- (10);
\end{tikzpicture}

\end{document}

図3

\documentclass[margin=0.5cm]{standalone}
\usepackage{tikz,newtxtext,newtxmath}
\usetikzlibrary{graphs,graphdrawing,calc}
\usegdlibrary{trees,force,circular}
\begin{document}

\begin{tikzpicture}[
    nodes={draw,fill=white,circle,minimum size=0.65cm,inner sep=0.1cm},
    foo/.style={-latex},
    lose/.style={fill=blue!70,text=white},
    win/.style={fill=red!70,text=white},
  ]
  \node (0) {};
  \node (1) at ($(0)+(60:1)$) {};
  \node (2) at ($(0)+(0:1)$) {};
  \node (3) at ($(1)+(0:1)$) {};
  \node[win] (4) at ($(3)+(30:1)$) {W};
  \node[win] (5) at ($(3)+(-30:1)$) {W};
  \node[lose] (6) at ($(4)+(90:1)$) {L};
  \node[lose] (7) at ($(5)+(-90:1)$) {L};
  \node (8) at ($(5)+(30:1)$) {};
  \node[win] (9) at ($(7)+(-90:1)$) {W};
  \node[lose] (10) at ($(9)+(-90:1)$) {L};
  \node (11) at ($(9)+cos(30)*(1,0)$) {};

  \draw [foo] (0) -- (1);
  \draw [foo] (1) -- (2);
  \draw [foo] (2) -- (0);
  \draw [foo] (2) -- (9);
  \draw [foo] (3) -- (1);
  \draw [foo] (4) -- (3);
  \draw [foo] (5) -- (3);
  \draw [foo] (4) -- (6);
  \draw [foo] (5) -- (7);
  \draw [foo] (8) -- (4);
  \draw [foo] (8) -- (5);
  \draw [foo] (11) -- (8);
  \draw [foo] (9) -- (11);
  \draw [foo] (9) -- (10);
\end{tikzpicture}

\end{document}

図4

\documentclass[margin=0.5cm]{standalone}
\usepackage{tikz,newtxtext,newtxmath}
\usetikzlibrary{graphs,graphdrawing,calc}
\usegdlibrary{trees,force,circular}
\begin{document}

\begin{tikzpicture}[
    nodes={draw,fill=white,circle,minimum size=0.65cm,inner sep=0.1cm},
    foo/.style={-latex},
    lose/.style={fill=blue!70,text=white},
    win/.style={fill=red!70,text=white},
  ]
  \node (0) {};
  \node (1) at ($(0)+(60:1)$) {};
  \node (2) at ($(0)+(0:1)$) {};
  \node (3) at ($(1)+(0:1)$) {};
  \node[win] (4) at ($(3)+(30:1)$) {W};
  \node[win] (5) at ($(3)+(-30:1)$) {W};
  \node[lose] (6) at ($(4)+(90:1)$) {L};
  \node[lose] (7) at ($(5)+(-90:1)$) {L};
  \node[lose] (8) at ($(5)+(30:1)$) {L};
  \node[win] (9) at ($(7)+(-90:1)$) {W};
  \node[lose] (10) at ($(9)+(-90:1)$) {L};
  \node (11) at ($(9)+cos(30)*(1,0)$) {};

  \draw [foo] (0) -- (1);
  \draw [foo] (1) -- (2);
  \draw [foo] (2) -- (0);
  \draw [foo] (2) -- (9);
  \draw [foo] (3) -- (1);
  \draw [foo] (4) -- (3);
  \draw [foo] (5) -- (3);
  \draw [foo] (4) -- (6);
  \draw [foo] (5) -- (7);
  \draw [foo] (8) -- (4);
  \draw [foo] (8) -- (5);
  \draw [foo] (11) -- (8);
  \draw [foo] (9) -- (11);
  \draw [foo] (9) -- (10);
\end{tikzpicture}

\end{document}

図5

\documentclass[margin=0.5cm]{standalone}
\usepackage{tikz,newtxtext,newtxmath}
\usetikzlibrary{graphs,graphdrawing,calc}
\usegdlibrary{trees,force,circular}
\begin{document}

\begin{tikzpicture}[
    nodes={draw,fill=white,circle,minimum size=0.65cm,inner sep=0.1cm},
    foo/.style={-latex},
    lose/.style={fill=blue!70,text=white},
    win/.style={fill=red!70,text=white},
  ]
  \node (0) {};
  \node (1) at ($(0)+(60:1)$) {};
  \node (2) at ($(0)+(0:1)$) {};
  \node (3) at ($(1)+(0:1)$) {};
  \node[win] (4) at ($(3)+(30:1)$) {W};
  \node[win] (5) at ($(3)+(-30:1)$) {W};
  \node[lose] (6) at ($(4)+(90:1)$) {L};
  \node[lose] (7) at ($(5)+(-90:1)$) {L};
  \node[lose] (8) at ($(5)+(30:1)$) {L};
  \node[win] (9) at ($(7)+(-90:1)$) {W};
  \node[lose] (10) at ($(9)+(-90:1)$) {L};
  \node[win] (11) at ($(9)+cos(30)*(1,0)$) {W};

  \draw [foo] (0) -- (1);
  \draw [foo] (1) -- (2);
  \draw [foo] (2) -- (0);
  \draw [foo] (2) -- (9);
  \draw [foo] (3) -- (1);
  \draw [foo] (4) -- (3);
  \draw [foo] (5) -- (3);
  \draw [foo] (4) -- (6);
  \draw [foo] (5) -- (7);
  \draw [foo] (8) -- (4);
  \draw [foo] (8) -- (5);
  \draw [foo] (11) -- (8);
  \draw [foo] (9) -- (11);
  \draw [foo] (9) -- (10);
\end{tikzpicture}

\end{document}

感想

後退解析という名前がしっくりこない。node 内の文字サイズによって頂点サイズが変わるの不便だと感じてたけど、inner sep=0 にして minimum size を設定すると綺麗になりそうだということが判明した。気が向いたら直す。

ARC 089 D. Checker

https://beta.atcoder.jp/contests/arc089/tasks/arc089_b

この解説では、座標を(横,縦)で表している。

$(x,y)$ が黒であることと $(x \bmod 2K, y \bmod 2K)$ が黒であることは同値である。
$(x,y)$ が白であることと $(x+K,y)$ が黒であることは同値である。


f:id:pekempey:20180124212659p:plain
図1. 同値変換によって $2K \times 2K$ の領域に条件を移動できる($K=2$)。白の条件は黒の条件に言い換えられるため、黒しかない場合に還元できる。


f:id:pekempey:20180124191918p:plain
図2. 盤面をコピーすることで範囲が単純になる。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
  int n, k;
  cin >> n >> k;
  vector<vector<int>> s(4 * k + 1, vector<int>(4 * k + 1));

  for (int i = 0; i < n; i++) {
    int x, y;
    char c;
    cin >> x >> y >> c;
    if (c == 'W') {
      x += k;
    }
    x %= 2 * k;
    y %= 2 * k;
    s[x + 1][y + 1]++;
    s[x + 2 * k + 1][y + 1]++;
    s[x + 1][y + 2 * k + 1]++;
    s[x + 2 * k + 1][y + 2 * k + 1]++;
  }

  for (int i = 0; i + 1 < s.size(); i++) {
    for (int j = 0; j + 1 < s.size(); j++) {
      s[i + 1][j + 1] += s[i + 1][j] + s[i][j + 1] - s[i][j];
    }
  }

  auto sum = [&](int y, int x, int n) {
    return s[y + n][x + n] - s[y + n][x] - s[y][x + n] + s[y][x];
  };

  int ans = 0;
  for (int i = 0; i < 2 * k; i++) {
    for (int j = 0; j < 2 * k; j++) {
      int s1 = sum(i, j, k);
      int s2 = sum(i + k, j + k, k);
      ans = max(ans, s1 + s2);
    }
  }
  cout << ans << endl;
}

図1のコード

\documentclass[dvipdfmx,margin=1cm]{standalone}

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

\usetikzlibrary{calc}
\usetikzlibrary{patterns}

\begin{document}

\begin{tikzpicture}[yscale=-1,
  foo/.style={circle,inner sep=0.07cm},
  ]

  \foreach \x/\y in {2/0, 6/0, 0/2, 4/2, 2/4, 6/4, 0/6, 4/6} {
    \draw[fill=black!10] (\x,\y) rectangle ++(2,2);
  }

  \draw[help lines] (-0.5,-0.5) grid (8.5,8.5);
  \draw[step=2] (-0.5,-0.5) grid (8.5,8.5);
  \draw[ultra thick] (0,0) rectangle (4,4);

  \node[fill=black,foo] (a) at ($(0,3) +(.5,.5)$) {};
  \node[fill=black,foo] (b) at ($(4,7) +(.5,.5)$) {};
  \draw[-latex,very thick] (b) to node [auto,xshift=-0.4cm] {$\bmod 2K$} (a);

  \node[fill=white,draw=black,foo] (c) at ($(5,1) +(.5,.5)$) {};
  \node[fill=black,foo] (d) at ($(7,1) +(.5,.5)$) {};
  \node[fill=black,foo] (e) at ($(3,1) +(.5,.5)$) {};
  \draw[-latex,very thick] (c) to node [auto] {$+K$} (d);
  \draw[-latex,very thick] (d) to [bend right=30] node [auto,xshift=-0.1cm] {$\bmod 2K$} (e);

  \draw (0,0) to [very thick,bend right=20] node [auto] {$2K$} (4,0);
  \draw (0,0) to [very thick,bend left=20] node [auto,swap] {$2K$} (0,4);

\end{tikzpicture}

\end{document}

図 2 のコード

% pgfmanual v3.0.1a
\documentclass[dvipdfmx,margin=1cm]{standalone}

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

\usetikzlibrary{calc}
\usetikzlibrary{patterns}
\begin{document}

\begin{tikzpicture}[yscale=-1]
  \begin{scope}[shift={(0,2)},local bounding box=scope1]
    \draw [help lines] (-0.5,-0.5) grid (4.5,4.5);
    \draw [step=2] (-0.5,-0.5) grid (4.5,4.5);
    \draw [very thick] (0,0) rectangle (4,4);

    \foreach \dy/\dx in {0/0} {
      \foreach \x/\y in {1/0, 3/1, 2/3}{
        \draw [fill=black,circle] ($(\x,\y) + (.5,.5) + (\dx,\dy)$) circle[radius=0.1cm];
      }
    }

    % pattern=crosshatch dots -- See pgfmanual p.666
    \draw [ultra thick,pattern=crosshatch dots] (1,2) rectangle (3,4);
    \draw [ultra thick,pattern=crosshatch dots] (0,0) rectangle (1,2);
    \draw [ultra thick,pattern=crosshatch dots] (3,0) rectangle (4,2);

    \draw [-latex,line width=0.1cm] (0.5,1.5) -- (1,2);
  \end{scope}

  \begin{scope}[shift={(10,0)},local bounding box=scope2]
    \draw [fill=black!20] (0,0) rectangle (4,4);
    \draw [fill=red!20] (4,0) rectangle (8,4);
    \draw [fill=blue!20] (0,4) rectangle (4,8);
    \draw [fill=green!20] (4,4) rectangle (8,8);

    \draw [help lines] (-0.5,-0.5) grid (8.5,8.5);
    \draw [step=2] (-0.5,-0.5) grid (8.5,8.5);
    \draw [very thick] (0,0) rectangle (4,4);

    \foreach \dy/\dx in {0/0, 0/4, 4/0, 4/4} {
      \foreach \x/\y in {1/0, 3/1, 2/3}{
        \draw [fill=black,circle] ($(\x,\y) + (.5,.5) + (\dx,\dy)$) circle[radius=0.1cm];
      }
    }

    \draw [-latex,ultra thick] (2,0) to [bend right=30] node [auto] {Copy} (6,0);
    \draw [-latex,ultra thick] (0,2) to [bend left=30] node [auto,swap] {Copy} (0,6);
    \draw [-latex,ultra thick] (2,8) to [bend left=30] node [auto,swap] {Copy} (6,8);

    \draw [ultra thick,pattern=crosshatch dots] (1,2) rectangle (3,4);
    \draw [ultra thick,pattern=crosshatch dots] (3,4) rectangle (5,6);

    \draw [-latex,line width=0.1cm] (0.5,1.5) -- (1,2);
  \end{scope}

  \draw [-latex,ultra thick] ($(scope1.east)+(0.5,0)$) -- node [auto] {Transform} ($(scope2.west)-(0.5,0)$);

\end{tikzpicture}

\end{document}

CF #458 E. Palindromes in a Tree

重心を求めるコードが間違っていたので修正しました(sz[v] >= x / 2ではなくsz[v] > x / 2が正しい)。計算量に影響はないです。2018-01-22 21:25

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

重心分解による分割統治法で解く。重心を c としたとき、回文パスは c を通るものと通らないものに分けることができる。c を通らないものに関しては部分問題で処理することにして、c を通るものに関して処理する。始点が u であるようなパスがいくつあるかが数えられるので、パスu-cにパターン数を加算すると良い。


f:id:pekempey:20180124000402p:plain
$c$ を通るパスは $u\to c$ と$c\to v$ に分割できるので、独立に処理できる。

回文かどうかの判定はビットマスクを使うとやりやすい。

#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);
  }
}

図のコード。TikZ

% 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{shadows} % pgfmanual.pdf p.689
\usetikzlibrary{shapes.geometric}

\begin{document}

\begin{tikzpicture}[
  foo/.style={fill=black,draw=none,text=white,drop shadow,shape=circle},
  bar/.style={fill=white,draw=black,text=white,drop shadow,shape=isosceles triangle},
  baz/.style={fill=red,draw=none,text=white,drop shadow,shape=circle},
  ]

  \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°単位でしか回転できないらしい。