{"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 be palindromic if at least one permutation of the labels in the path is a palindrome.\n\nFor each vertex, output the number of palindromic paths passing through it.\n\n**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.\n\n## Input\n\nThe first line contains an integer _n_ (2 ≤ _n_ ≤ 2·105) — the number of vertices in the tree.\n\nThe 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.\n\nThe 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.\n\n## Output\n\nPrint _n_ integers in a single line, the _i_\\-th of which is the number of palindromic paths passing through vertex _i_ in the tree.\n\n[samples]\n\n## Note\n\nIn the first sample case, the following paths are palindromic:\n\n2 - 3 - 4\n\n2 - 3 - 5\n\n4 - 3 - 5\n\nAdditionally, all paths containing only one vertex are palindromic. Listed below are a few paths in the first sample that are not palindromic:\n\n1 - 2 - 3\n\n1 - 2 - 3 - 4\n\n1 - 2 - 3 - 5","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] 的路径与从顶点 #cf_span[v] 到顶点 #cf_span[u] 的路径视为相同，且该路径仅对它经过的每个顶点计数一次。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 2·105]) —— 树中顶点的数量。\n\n接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1  ≤  u, v  ≤  n, u ≠ v])，表示连接顶点 #cf_span[u] 和顶点 #cf_span[v] 的边。保证给定的图是一棵树。\n\n下一行包含一个由 #cf_span[n] 个小写字母（从 _a_ 到 _t_）组成的字符串，其中第 #cf_span[i]-th (#cf_span[1 ≤ i ≤ n]) 个字符是树中顶点 #cf_span[i] 的标签。\n\n请在一行中输出 #cf_span[n] 个整数，第 #cf_span[i]-th 个整数表示经过顶点 #cf_span[i] 的回文路径数量。\n\n在第一个样例中，以下路径是回文的：\n\n#cf_span[2 - 3 - 4]\n\n#cf_span[2 - 3 - 5]\n\n#cf_span[4 - 3 - 5]\n\n此外，所有仅包含一个顶点的路径都是回文的。以下是一些第一个样例中非回文的路径：\n\n#cf_span[1 - 2 - 3]\n\n#cf_span[1 - 2 - 3 - 4]\n\n#cf_span[1 - 2 - 3 - 5]\n\n## Input\n\n第一行包含一个整数 #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] 的标签。\n\n## Output\n\n请在一行中输出 #cf_span[n] 个整数，第 #cf_span[i]-th 个整数表示经过顶点 #cf_span[i] 的回文路径数量。\n\n[samples]\n\n## Note\n\n在第一个样例中，以下路径是回文的：#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]","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| = 20 $.\n- 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 $.\n- A path $ P $ is *palindromic* if the multiset of labels $ \\{\\ell(v_i) \\mid v_i \\in P\\} $ can be rearranged into a palindrome.\n\n**Given:**\n- $ n \\in \\mathbb{N} $, $ 2 \\leq n \\leq 2 \\cdot 10^5 $\n- Tree $ T $ with $ n-1 $ edges\n- String $ s \\in \\Sigma^n $, where $ s[i] = \\ell(i+1) $\n\n**Objective:**\nFor each vertex $ v \\in V $, compute:\n$$\nf(v) = \\left| \\left\\{ P \\text{ is a path in } T \\,\\middle|\\, v \\in P \\text{ and } P \\text{ is palindromic} \\right\\} \\right|\n$$\n\n**Palindromic Condition (Formal):**\nA multiset of characters $ M $ can form a palindrome if and only if at most one character in $ M $ has an odd frequency.\n\nEquivalently, 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.\n\nThen $ 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).\n\n**Output:**\nA list $ [f(1), f(2), \\dots, f(n)] $ of integers.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF914E","tags":["bitmasks","data structures","divide and conquer","trees"],"sample_group":[["5\n1 2\n2 3\n3 4\n3 5\nabcbb","1 3 4 3 3"],["7\n6 2\n4 3\n3 7\n5 2\n7 2\n1 4\nafefdfs","1 4 1 1 2 4 2"]],"created_at":"2026-03-03 11:00:39"}}