CF 106260B - 回文

Rating: -
Tags: -
Solve time: 48s
Verified: yes

Solution

Problem Understanding

We are given a rooted tree where each node carries a lowercase letter. The root is node 1, and every node has a well-defined depth from the root.

Each query focuses on one node u and a target depth d. We look at all nodes that satisfy two conditions at the same time: they lie inside the subtree of u, and their depth from the root is exactly d. From the letters written on those nodes, we form a string using all of them in any order.

The question for each query is whether we can reorder those letters so that the resulting string becomes an anti-palindrome, meaning that if we pair the first character with the last, second with second last, and so on, no pair contains the same letter.

The tree size and number of queries are both large enough that any per-query traversal of a subtree is too slow. Visiting nodes inside each subtree separately would lead to roughly $O(nq)$, which is far beyond feasible limits for $2 \cdot 10^5$. This forces us into a preprocessing approach where subtree and depth information is reorganized so queries reduce to fast range counting.

A subtle edge case appears when there are no nodes matching a query condition. For example, if no node in the subtree of u lies at depth d, the answer must be “No”. Another important case is when only a single node exists in that layer: a single character string cannot form an anti-palindrome because it would compare against itself in the middle position. For instance, a single node with letter "a" must return No.

Approaches

A direct approach for each query would be to collect all nodes in the subtree of u, filter those with depth d, extract their letters, and then check whether we can arrange them into an anti-palindrome. The correctness is straightforward because it mirrors the definition exactly. The issue is performance. In a dense tree, a subtree may contain $O(n)$ nodes, and doing this for every query leads to $O(nq)$ work, which is too large.

The key structural observation is that the condition “node is in subtree of u” is naturally represented by Euler tour intervals, while “node has depth d” partitions nodes into independent layers. Once we fix a depth d, all nodes at that depth can be listed in increasing order of entry time in the Euler tour. Then every subtree restriction becomes a contiguous interval query on that sorted list.

This reduces the problem to a frequency query on a static array per depth. For each depth, we maintain a list of nodes sorted by their DFS entry time, and also maintain prefix counts of letters over that list. Then each query becomes extracting a frequency table over a subarray, which can be done in O(26) time.

The remaining step is checking whether a multiset of letters can form an anti-palindrome. A multiset can be rearranged so that no mirrored pair matches if and only if the length is even and no character appears more than half the length. If any character exceeds half, it must inevitably occupy two mirrored positions.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force per query	$O(n)$ per query	$O(n)$	Too slow
DFS + depth lists + prefix counts	$O((n+q)\log n + 26q)$	$O(n)$	Accepted

Algorithm Walkthrough

Run a DFS from the root to compute two values for each node: its depth and its Euler entry time. This linearizes the subtree structure so that every subtree becomes an interval in DFS order.
For each depth value d, collect all nodes that lie at this depth. Store them in increasing order of their DFS entry time. This ensures that any subtree restriction will correspond to a contiguous segment inside this list.
For every depth list, build 26 prefix arrays, one per letter. Each prefix array allows us to count occurrences of a letter in any segment in constant time.
For each query (u, d), locate the segment of nodes at depth d whose entry times lie between tin[u] and tout[u] using binary search.
Using prefix differences, compute the frequency of each character in that segment.
Let k be the total number of nodes in this segment. If k == 0, output “No”.
If k is odd, output “No” because an anti-palindrome requires pairing every position with a distinct partner.
Otherwise, check whether any character frequency exceeds k / 2. If such a character exists, output “No”, otherwise output “Yes”.

Why it works

The DFS ordering guarantees that subtree membership becomes an interval condition. The depth grouping isolates each query into a single layer where structure no longer depends on the tree, only on positions in DFS order. Within a fixed layer, prefix sums make frequency extraction exact for any subtree slice.

The anti-palindrome condition reduces to pairing positions symmetrically. Since every position must be paired with a distinct position, no character can dominate more than half the slots, and even length is required for complete pairing. These two conditions fully characterize feasibility.

Python Solution

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**7)

n, q = map(int, input().split())
g = [[] for _ in range(n + 1)]

for _ in range(n - 1):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

s = input().strip()

tin = [0] * (n + 1)
tout = [0] * (n + 1)
depth = [0] * (n + 1)
timer = 0

nodes_by_depth = {}

def dfs(u, p):
    global timer
    timer += 1
    tin[u] = timer

    d = depth[u]
    if d not in nodes_by_depth:
        nodes_by_depth[d] = []
    nodes_by_depth[d].append(u)

    for v in g[u]:
        if v == p:
            continue
        depth[v] = d + 1
        dfs(v, u)

    tout[u] = timer

dfs(1, -1)

# build depth structures
depth_data = {}
for d, nodes in nodes_by_depth.items():
    nodes.sort(key=lambda x: tin[x])
    arr = [s[u - 1] for u in nodes]

    pref = [[0] * (len(nodes) + 1) for _ in range(26)]
    for i, ch in enumerate(arr, 1):
        for c in range(26):
            pref[c][i] = pref[c][i - 1]
        pref[ord(ch) - 97][i] += 1

    depth_data[d] = (nodes, pref)

def solve_query(u, d):
    if d not in depth_data:
        return False

    nodes, pref = depth_data[d]

    # find left bound: first tin >= tin[u]
    l, r = 0, len(nodes)
    while l < r:
        m = (l + r) // 2
        if tin[nodes[m]] >= tin[u]:
            r = m
        else:
            l = m + 1
    left = l

    # find right bound: last tin <= tout[u]
    l, r = 0, len(nodes)
    while l < r:
        m = (l + r) // 2
        if tin[nodes[m]] <= tout[u]:
            l = m + 1
        else:
            r = m
    right = l

    k = right - left
    if k == 0:
        return False
    if k % 2 == 1:
        return False

    for c in range(26):
        cnt = pref[c][right] - pref[c][left]
        if cnt > k // 2:
            return False

    return True

out = []
for _ in range(q):
    u, d = map(int, input().split())
    out.append("Yes" if solve_query(u, d) else "No")

print("\n".join(out))

The DFS section constructs a linear order where subtree queries become range constraints. The per-depth preprocessing compresses the problem into independent frequency arrays.

Inside each query, the two binary searches isolate exactly the nodes belonging to both the subtree and the target depth. The prefix arrays then allow exact counting without scanning the segment.

The final checks implement the structural constraints of anti-palindromes: even length and bounded frequency.

Worked Examples

Consider a small tree where node 1 has children 2 and 3, and both 2 and 3 have one child each. Suppose we query a subtree that includes two nodes at the same depth with letters a and b.

Step	Nodes considered	Letters	Frequency check	Result
Query subtree-depth slice	[2, 3]	a, b	max freq = 1	Yes

This shows a valid pairing ab.

Now consider a case where all nodes at that depth are a.

Step	Nodes considered	Letters	Frequency check	Result
Query subtree-depth slice	[2, 3, 4, 5]	a, a, a, a	max freq = 4	No

Even though the length is even, any arrangement forces a to match with a in some mirrored position.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(n \log n + q \log n + 26q)$	DFS builds structure; each query uses two binary searches and 26 counts
Space	$O(26n)$	prefix arrays per depth store cumulative counts

The preprocessing is linear in the number of nodes up to sorting overhead per depth list. Each query only performs logarithmic boundary finding plus constant alphabet scanning, which fits comfortably under constraints for $2 \cdot 10^5$ operations.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys as _sys
    from collections import defaultdict

    # paste solution here or assume callable solve()
    return ""

# custom cases
assert run("""5 1
1 2
1 3
2 4
2 5
aabcc
1 2
""").strip().lower() == "yes"

assert run("""3 1
1 2
1 3
aaa
1 2
""").strip().lower() == "no"

assert run("""4 1
1 2
1 3
1 4
abca
1 3
""").strip().lower() in {"yes","no"}

Test input	Expected output	What it validates
small subtree valid mix	Yes	basic feasibility
uniform letters	No	frequency dominance failure
sparse depth slice	depends	empty/edge depth handling

Edge Cases

A subtree query where no node exists at the target depth reduces to an empty segment after binary search. In that case the computed length k becomes zero and the algorithm directly returns “No”, matching the requirement that no valid rearrangement exists.

A single-node segment always fails because k = 1, which is odd. The algorithm rejects it immediately without frequency checks, correctly capturing that a self-paired position cannot satisfy the anti-palindrome constraint.

A case where one character dominates the entire depth slice, such as aaaaab, triggers the cnt > k/2 condition. Even though the segment may be large enough and even-length, at least one mirrored pair must match, so the rejection is necessary and correctly handled by the frequency bound.