树上的回文

Question

我正在看这个挑战：

Given a tree with N nodes and N-1 edges. Each edge on the tree is labelled by a string of lowercase letters from the Latin alphabet. Given Q queries, consisting of two nodes u and v, check if it is possible to make a palindrome string which uses all the characters that belong to the string labelled on the edges in the path from node u to node v.

Characters can be used in any order.

N is of the order of 10⁵ and Q is of the order of 10⁶

Input:

N=3
u=1 v=3 weight=bc
u=1 v=2 weight=aba
Q=4
u=1 v=2
u=2 v=3
u=3 v=1
u=3 v=3

Output:

YES
YES
NO
NO

我想的是通过在 O(1) 中使用稀疏 table 和欧拉塔上的范围最小查询进行预计算来计算 2 个节点之间的 LCA，然后查看从 LCA 到节点 u 和 LCA 到节点 v 的路径并存储所有字符频率。如果所有字符的频率之和为奇数，我们检查除一个字符之外的每个字符的频率是否为奇数。如果所有字符的频率之和是偶数，我们检查每个字符的频率是否是偶数。但是这个过程肯定会超时，因为Q可以达到10⁶.

有没有人有更好的算法？

Answer 1

准备步骤

按如下方式准备数据结构：

为每个节点获取到根的路径，获取路径上的所有字母，并且仅当字母在该路径上出现奇数次时才保留该字母。最后用唯一字母将该字符串编码为位模式，其中当有 "a" 时设置第 0 位，当有 "b" 时设置第 1 位，...当有 "b" 时设置第 25 位是一个"z"。将此模式与节点一起存储。

此预处理可以通过深度优先递归过程完成，其中当前节点的模式被传递给子节点，子节点可以将边的信息应用于该模式以创建自己的模式。因此，就树中的字符总数而言，此预处理可以在线性时间内运行，或更准确地说 O(N+S)，其中 S表示该字符总数。

查询步骤

查询完成后，对涉及的两个模式执行按位异或。如果结果为 0 或仅设置了一位，则 return "YES"，否则 return "NO"。因此查询将不会访问任何其他节点，而不仅仅是给定的两个节点，查找这两个模式并执行它们的 XOR 并进行位测试。所有这一切都发生在一个查询的恒定时间内。

题中给出的最后一个查询表明，当两个节点是同一个节点时，结果应该是"NO"。这是一个边界情况，因为空字符串是否是回文是有争议的。上面的 XOR 算法将 return "YES"，因此您需要针对这种边界情况进行特定测试，而 return "NO" 代替。

说明

这是可行的，因为如果我们查看两个节点到根的路径，它们可能共享其路径的一部分。不应考虑该公共路径上的字符，并且 XOR 将确保它们不是。在路径不同的地方，我们实际上在从一个节点到另一个节点的路径上有边。在那里我们看到了应该构成回文的字符。

如果一个字符在这些边上出现的次数为偶数次，则创建回文没有问题。 XOR 确保这些字符 "disappear".

如果一个字符出现奇数次，除了一个字符之外的所有字符都可以像 even 的情况一样相互镜像。剩下的那个只能用在奇数长度的回文中，而且只能用在它的中心位置。所以这样的角色只能有一个。这转化为允许 XOR 结果设置 1 位（但不能更多）的测试。

实施

这是 JavaScript 中的一个实现。示例运行使用问题中提供的输入。我懒得把查询结果从 boolean 变成 NO/YES:

function prepare(edges) {
    // edges: array of [u, v, weight] triplets
    // Build adjacency list from the list of edges
    let adjacency = {};
    for (let [u, v, weight] of edges) {
        // convert weight to pattern, as we don't really need to 
        //   store the strings
        let pattern = 0;
        for (let i = 0; i < weight.length; i++) {
            let ascii = weight.charCodeAt(i) - 97;
            pattern ^= 1 << ascii; // toggle bit that corresponds to letter
        }
        if (v in adjacency && u in adjacency) throw "Cycle detected!";
        if (!(v in adjacency)) adjacency[v] = {};
        if (!(u in adjacency)) adjacency[u] = {};
        adjacency[u][v] = pattern;
        adjacency[v][u] = pattern;
    }
    
    // Prepare the consolidated path-pattern for each node
    let patterns = {}; // This is the information to return

    function dfs(u, parent, pathPattern) {
        patterns[u] = pathPattern;
        for (let v in adjacency[u]) {
            // recurse into the "children" (the parent is not revisited)
            if (v !== parent) dfs(v, u, adjacency[u][v] ^ pathPattern);
        }
    }
    
    // Start a DFS from an arbitrary node as root
    dfs(edges[0][0], null, 0);
    return patterns;
}

function query(nodePatterns, u, v) {
    if (u === v) return false; // Boundary case.
    let pattern = nodePatterns[u] ^ nodePatterns[v];
    // "smart" test to verify that at most 1 bit is set
    return pattern === (pattern & -pattern); 
}

// Example:
let edges = [[1, 3, "bc"], [1, 2, "aba"]];
let queries = [[1, 2], [2, 3], [3, 1], [3, 3]];

let nodePatterns = prepare(edges);
for (let [u, v] of queries) {
    console.log(u, v, query(nodePatterns, u, v));
}

Answer 2

首先，让我们选择一个根。现在想象一下，每条边都指向树中更深的一个节点。不要在边上放置字符串，而是将它们放在这些边指向的顶点上。现在你的根没有字符串了。现在为每个顶点计算每个字母的数量并将其存储在它的字符串中。

从现在开始，我们将分别为每个字母做一些事情。使用 DFS，为每个节点 v 计算从 v 到根的路径上的顶点上的字母数。您还需要 LCA，因此您可以根据需要预先计算 RMQ 或在 O(logn) 中查找 LCA。令 Letters[v][c] 为从 v 到根的路径上的字母 c 的数量。然后，要找到从 u 到 v 的字母 c 的数量，只需使用 Letters[v][c] + Letters[u][c] - 2 * Letters[LCA(v, u)][c]。您可以在 O(1) 中检查单个字母的数量（如果您不使用 RMQ，则为 O(logn)）。所以在 26* O(1) 中你可以检查每一个可能的字母。

树上的回文

Palindromes in a tree

algorithm

tree

time-complexity

lowest-common-ancestor

Input:

Output:

准备步骤

查询步骤

说明

实施