E. Palindromes in a Tree

Codeforces

IDCF914E

Time4000ms

Memory256MB

Difficulty—

bitmasksdata structuresdivide and conquertrees

English · Original

Chinese · Translation

Formal · Original

You are given a tree (a connected acyclic undirected graph) of _n_ vertices. Vertices are numbered from 1 to _n_ and each vertex is assigned a character from _a_ to _t_. A path in the tree is said to be palindromic if at least one permutation of the labels in the path is a palindrome. For each vertex, output the number of palindromic paths passing through it. **Note:** The path from vertex _u_ to vertex _v_ is considered to be the same as the path from vertex _v_ to vertex _u_, and this path will be counted only once for each of the vertices it passes through. ## Input The first line contains an integer _n_ (2 ≤ _n_ ≤ 2·105) — the number of vertices in the tree. The next _n_ - 1 lines each contain two integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _n_, _u_ ≠ _v_) denoting an edge connecting vertex _u_ and vertex _v_. It is guaranteed that the given graph is a tree. The next line contains a string consisting of _n_ lowercase characters from _a_ to _t_ where the _i_\-th (1 ≤ _i_ ≤ _n_) character is the label of vertex _i_ in the tree. ## Output Print _n_ integers in a single line, the _i_\-th of which is the number of palindromic paths passing through vertex _i_ in the tree. [samples] ## Note In the first sample case, the following paths are palindromic: 2 - 3 - 4 2 - 3 - 5 4 - 3 - 5 Additionally, all paths containing only one vertex are palindromic. Listed below are a few paths in the first sample that are not palindromic: 1 - 2 - 3 1 - 2 - 3 - 4 1 - 2 - 3 - 5

你被给定一棵树（一个连通的无环无向图），包含 #cf_span[n] 个顶点。顶点编号从 #cf_span[1] 到 #cf_span[n]，每个顶点被分配一个从 _a_ 到 _t_ 的字符。树中的一条路径被称为回文路径，当且仅当该路径上所有标签的至少一个排列构成一个回文串。对于每个顶点，输出经过它的回文路径的数量。 *注意*：从顶点 #cf_span[u] 到顶点 #cf_span[v] 的路径与从顶点 #cf_span[v] 到顶点 #cf_span[u] 的路径视为相同，且该路径仅对它经过的每个顶点计数一次。第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 2·105]) —— 树中顶点的数量。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n, u ≠ v])，表示连接顶点 #cf_span[u] 和顶点 #cf_span[v] 的边。保证给定的图是一棵树。下一行包含一个由 #cf_span[n] 个小写字母（从 _a_ 到 _t_）组成的字符串，其中第 #cf_span[i]-th (#cf_span[1 ≤ i ≤ n]) 个字符是树中顶点 #cf_span[i] 的标签。请在一行中输出 #cf_span[n] 个整数，第 #cf_span[i]-th 个整数表示经过顶点 #cf_span[i] 的回文路径数量。在第一个样例中，以下路径是回文的： #cf_span[2 - 3 - 4] #cf_span[2 - 3 - 5] #cf_span[4 - 3 - 5] 此外，所有仅包含一个顶点的路径都是回文的。以下是一些第一个样例中非回文的路径： #cf_span[1 - 2 - 3] #cf_span[1 - 2 - 3 - 4] #cf_span[1 - 2 - 3 - 5] ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 2·105]) —— 树中顶点的数量。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n, u ≠ v])，表示连接顶点 #cf_span[u] 和顶点 #cf_span[v] 的边。保证给定的图是一棵树。下一行包含一个由 #cf_span[n] 个小写字母（从 _a_ 到 _t_）组成的字符串，其中第 #cf_span[i]-th (#cf_span[1 ≤ i ≤ n]) 个字符是树中顶点 #cf_span[i] 的标签。 ## Output 请在一行中输出 #cf_span[n] 个整数，第 #cf_span[i]-th 个整数表示经过顶点 #cf_span[i] 的回文路径数量。 [samples] ## Note 在第一个样例中，以下路径是回文的：#cf_span[2 - 3 - 4]#cf_span[2 - 3 - 5]#cf_span[4 - 3 - 5]此外，所有仅包含一个顶点的路径都是回文的。以下是一些第一个样例中非回文的路径：#cf_span[1 - 2 - 3]#cf_span[1 - 2 - 3 - 4]#cf_span[1 - 2 - 3 - 5]

**Definitions:** - Let $ T = (V, E) $ be a tree with $ |V| = n $, $ V = \{1, 2, \dots, n\} $. - Let $ \ell: V \to \Sigma $ be a labeling function, where $ \Sigma = \{a, b, \dots, t\} $, $ |\Sigma| = 20 $. - A path $ P $ between two vertices is a sequence of distinct vertices $ v_1, v_2, \dots, v_k $ such that consecutive vertices are adjacent in $ T $. - A path $ P $ is *palindromic* if the multiset of labels $ \{\ell(v_i) \mid v_i \in P\} $ can be rearranged into a palindrome. **Given:** - $ n \in \mathbb{N} $, $ 2 \leq n \leq 2 \cdot 10^5 $ - Tree $ T $ with $ n-1 $ edges - String $ s \in \Sigma^n $, where $ s[i] = \ell(i+1) $ **Objective:** For each vertex $ v \in V $, compute: $$ f(v) = \left| \left\{ P \text{ is a path in } T \,\middle|\, v \in P \text{ and } P \text{ is palindromic} \right\} \right| $$ **Palindromic Condition (Formal):** A multiset of characters $ M $ can form a palindrome if and only if at most one character in $ M $ has an odd frequency. Equivalently, define the *parity mask* of a path $ P $ as a 20-bit integer $ \mu(P) \in \{0,1\}^{20} $, where bit $ j $ is 1 if the frequency of the $ j $-th character in $ \Sigma $ (0-indexed) along $ P $ is odd, and 0 otherwise. Then $ P $ is palindromic $ \iff \mu(P) $ has at most one bit set (i.e., $ \mu(P) = 0 $ or $ \mu(P) $ is a power of two). **Output:** A list $ [f(1), f(2), \dots, f(n)] $ of integers.

Samples

Input #1

5
1 2
2 3
3 4
3 5
abcbb

Output #1

1 3 4 3 3

Input #2

7
6 2
4 3
3 7
5 2
7 2
1 4
afefdfs

Output #2

1 4 1 1 2 4 2

API Response (JSON)

{
  "problem": {
    "name": "E. Palindromes in a Tree",
    "description": {
      "content": "You are given a tree (a connected acyclic undirected graph) of _n_ vertices. Vertices are numbered from 1 to _n_ and each vertex is assigned a character from _a_ to _t_. A path in the tree is said to",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF914E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a tree (a connected acyclic undirected graph) of _n_ vertices. Vertices are numbered from 1 to _n_ and each vertex is assigned a character from _a_ to _t_.\n\nA path in the tree is said to...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定一棵树（一个连通的无环无向图），包含 #cf_span[n] 个顶点。顶点编号从 #cf_span[1] 到 #cf_span[n]，每个顶点被分配一个从 _a_ 到 _t_ 的字符。\n\n树中的一条路径被称为回文路径，当且仅当该路径上所有标签的至少一个排列构成一个回文串。\n\n对于每个顶点，输出经过它的回文路径的数量。\n\n*注意*：从顶点 #cf_span[u] 到顶点 #cf_span[v...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions:**\n- Let $ T = (V, E) $ be a tree with $ |V| = n $, $ V = \\{1, 2, \\dots, n\\} $.\n- Let $ \\ell: V \\to \\Sigma $ be a labeling function, where $ \\Sigma = \\{a, b, \\dots, t\\} $, $ |\\Sigma| = 2...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments