algorithm - 树中的回文

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)中进行预计算来计算2个节点之间的LCA，然后查看从LCA到节点u的路径和LCA到节点 v 并存储所有字符频率。如果所有字符的频率之和为奇数，我们检查除一个字符之外的每个字符的频率是否为奇数。如果所有字符的频率之和是偶数，我们检查每个字符的频率是否是偶数。但这个过程肯定会超时，因为 Q 最多可达 10⁶。

有没有人有更好的算法？

Answer 1

准备步骤

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

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

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

查询步骤

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

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

说明

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

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

如果一个字符出现奇数次，则除了一个字符之外的所有字符都可以相互镜像，就像偶数情况一样。剩下的一个只能用在奇数长度的回文中，并且只能用在它的中心位置。所以这样的角色只能有一个。这意味着 XOR 结果允许设置 1 位(但不能设置更多)的测试。

实现

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