2

我正在研究这个挑战：

给定一棵具有N个节点和N-1 条边的树。树上的每条边都由一串来自拉丁字母的小写字母标记。给定由两个节点u和v组成的Q个查询，检查是否有可能创建一个回文字符串，该字符串使用属于从节点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

输出：

是
是
否
否

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

有人有更好的算法吗？

4

2 回答 2

5

准备步骤

准备数据结构如下：

对于每个节点，获取到根的路径，获取路径上的所有字母，并且仅在该路径上出现奇数次时保留一个字母。最后用唯一字母将该字符串编码为位模式，其中当有“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));
}

于 2019-12-14T22:51:12.443 回答
0

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

从现在开始，我们将分别为每个字母做一些事情。使用 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) 中，您可以检查每个可能的字母。

于 2019-12-14T23:16:52.833 回答