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にパターン数を加算すると良い。

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