跳转至

3973. 通往最近公共祖先的不同门径 🔒

题目描述

给定一棵以节点 0 为根的无向树，共有 n 个节点，编号为 0 到 n - 1。树由数组 parent 表示，其中 parent[i] 表示节点 i 的父节点。

每个节点 i 都拥有三种类型的门，由二维数组 gates 给出，其中 gates[i] = [redi, bluei, whitei] 分别表示节点 i 上 红门、蓝门 和 白门 的数量。

  • 红门（Red）：只能使用 红卡 通过。
  • 蓝门（Blue）：只能使用 蓝卡 通过。
  • 白门（White）：可以使用 任意颜色 的卡通过，但通过后会 翻转 卡片颜色。

Alice 和 Bob 分别从给定节点出发，初始持有一张红卡或蓝卡（1 表示红卡，0 表示蓝卡）。两人需要 独立地 沿着树 向上移动，直到到达他们的 最近公共祖先（LCA）。

对于每一步移动，只有当当前节点存在至少一个能够被当前卡片使用的门时，才能从该节点移动到父节点。白门可以被使用任意次，每次都会翻转卡片颜色。

移动规则（一次移动指从 u 移动到 parent[u]）：

  • 只能沿树向上朝根节点移动。
  • 在节点 u，必须选择 恰好一个 具体的门实例。即使多个门类型相同，它们也视为 不同的门实例，分别计数。
  • 若当前持有 红卡：可以使用一个红门并保持红卡；或使用一个白门，并将卡片变为蓝卡。
  • 若当前持有 蓝卡：可以使用一个蓝门并保持蓝卡；或使用一个白门，并将卡片变为红卡。
  • 若当前节点不存在可使用的门，则移动序列立即终止。

同时给定一个二维数组 queries，其中 queries[i] = [aNodei, aCardi, bNodei, bCardi]：

  • aNodei、aCardi：表示 Alice 的起始节点及初始卡片。
  • bNodei、bCardi：表示 Bob 的起始节点及初始卡片。

对于每个查询，计算 Alice 和 Bob 分别成功到达其 最近公共祖先（LCA）的不同合法方案数，结果对 109 + 7 取模。

所有查询计算完成后，返回这些结果的 按位异或（bitwise XOR）值。

注意：

  • 若 Alice 或 Bob 任意一人的门使用方案不同，则认为两种方案不同。
  • 若某人起始时已经位于 LCA，则该人的方案数记为 1。
  • 最近公共祖先（LCA）定义为：节点 a 与节点 b 的最低公共祖先（节点本身也视为自己的祖先）。

 

示例 1：

输入： n = 3, parent = [-1,0,0], gates = [[1,0,1],[0,1,1],[1,1,0]], queries = [[1,0,2,0],[1,1,2,0],[1,0,2,1]]

输出： 1

解释：

i Alice
[节点, 卡片]		 Bob
[节点, 卡片]		 LCA Alice
路径		 Bob
路径		 Alice
方案数		 Bob
方案数		 总方案数
0 [1, 0]：蓝卡 [2, 0]：蓝卡 0 1 → 0 2 → 0 2（节点 1 的 1 个蓝门 + 1 个白门） 1（节点 2 的 1 个蓝门） 2 × 1 = 2
1 [1, 1]：红卡 [2, 0]：蓝卡 0 1 → 0 2 → 0 1（节点 1 的 1 个白门） 1（节点 2 的 1 个蓝门） 1 × 1 = 1
2 [1, 0]：蓝卡 [2, 1]：红卡 0 1 → 0 2 → 0 2（节点 1 的 1 个蓝门 + 1 个白门） 1（节点 2 的 1 个红门） 2 × 1 = 2

因此，所有结果按位异或为：2 XOR 1 XOR 2 = 1。

示例 2：

输入： n = 3, parent = [-1,0,1], gates = [[0,1,2],[1,0,1],[0,0,3]], queries = [[2,0,1,0],[2,1,0,0],[1,1,2,1]]

输出： 3

解释：

i Alice
[节点, 卡片]		 Bob
[节点, 卡片]		 LCA Alice 路径 Bob 路径 Alice 方案数 Bob 方案数 总方案数
0 [2, 0]：蓝卡 [1, 0]：蓝卡 1 2 → 1 1 3（节点 2 的 3 个白门） 1（无需移动） 3 × 1 = 3
1 [2, 1]：红卡 [0, 0]：蓝卡 0 2 → 1 → 0 0 3（节点 2 的 3 个白门）× 1（节点 1 的 1 个白门）= 3 1（无需移动） 3 × 1 = 3
2 [1, 1]：红卡 [2, 1]：红卡 1 1 2 → 1 1（无需移动） 3（节点 2 的 3 个白门） 1 × 3 = 3

因此，所有结果按位异或为：3 XOR 3 XOR 3 = 3。

 

提示​​​：

  • 2 <= n <= 2 * 104
  • n == parent.length == gates.length
  • parent[0] == -1
  • 对于 [1, n - 1] 中的 i，0 <= parent[i] < n
  • gates[i] == [redi, bluei, whitei]
  • 0 <= redi, bluei, whitei <= 10
  • 1 <= queries.length <= 2 * 104
  • queries[i] = [aNodei, aCardi, bNodei, bCardi]
  • 0 <= aNodei, bNodei <= n - 1
  • 0 <= aCardi, bCardi <= 1
  • 输入保证数组 parent 表示一棵合法的树。

解法

方法一

1


1


1


1

评论