树上的回文

Question

我正在考虑这个挑战：

给定具有N 个节点和N-1 条边的树。树上的每条边都用拉丁字母表中的一串小写字母标记。给定Q查询，由两个节点u和v 组成，检查是否可以创建一个回文字符串，该字符串使用属于从节点u到节点v的路径中边上标记的字符串的所有字符。

字符可以按任何顺序使用。

N是 10 ^{5 的数量级}，Q是 10 ^{6 的数量级}

输入：

N=3
u=1 v=3 重量=bc
u=1 v=2 重量=aba
Q=4
u=1 v=2
u=2 v=3
u=3 v=1
u=3 v=3

输出：

是
是
否
否

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

有人有更好的算法吗？

Answer 1

准备步骤

准备你的数据结构如下：

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

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

查询步骤

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

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

解释

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

如果字符在这些边缘出现偶数次，则创建回文没有问题。XOR 确保这些字符“消失”。

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

执行

这是 JavaScript 中的实现。示例运行使用问题中提供的输入。我没有费心将查询结果从布尔值转换为 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));
}