树中的非路径三元组计数

引言

在这个问题中，我们给定一棵树，它有 N 个顶点。在这棵树中，第 i 条边连接顶点 Ai 到顶点 Bi。在这个问题中，我们的任务是找到整数三元组 (i, j, k) 的数量，使得

• i < j < k 且 1 ≤ i, j, k ≤ N。
• 给定树不包含一条简单路径，该路径包含所有三个顶点：i, j 和 k。

示例-1

输入

给定输入是 N = 5, A[] = [1, 2, 2, 1], B[] = [2, 3, 4, 5]

输出

给定输入的输出是 2。

说明

在上述输入中，有两个满足条件的三元组：(i, j, k) = (1, 3, 4), (3, 4, 5)。

示例-2

输入

给定输入是 N = 6, A[] = [1, 2, 3, 4, 5], B[] = [2, 3, 4, 5, 6]

输出

给定输入的输出是 0。

方法

为了解决上述问题，我们必须遵循以下思路。

观察结果

在这种方法中，我们将创建一个方法来满足树结构中的某个条件，然后返回一个公式来计算涉及不动点的和。

• 条件： 条件的目标是避免树中简单路径上存在三个连续顶点 (a, b, c) 的情况。
• 不动点： 在一棵树中，当存在三个连续顶点时，我们必须将其视为树的不动点。借助这个不动点，我们可以满足上述条件。
• 连通分量： 我们可以将连通分量表示为 M。这里，M 存储了连通分量的大小，不包括指定的点 (m1, ..., mk)。
• 不动点之和： 我们可以借助公式 2 * Σ (i < j) mi * mj 来计算不动点之和。
• 转换

借助此，我们可以将公式转换为如下形式

2 * Σ (i < j) mi * mj = ( Σ mi ) 2 - Σ (mi) 2。

• 复杂度： 我们可以通过预先计算每个顶点 v 处根子树的大小，以 O(k) 的复杂度解决问题，整体复杂度为 O(n)。
• 不改变运算符： 借助这种方法，我们可以解决问题，而无需更改任何数学运算符。

解决问题所涉及的步骤

我们可以通过一些步骤来解决问题。它们如下所示

1. 首先，我们必须创建一个空的邻接列表 'T'，它表示树结构。树中有一些边，在所有边中，我们必须添加相应的顶点。这看起来像一个连接。
2. 然后我们必须将变量 'ans' 初始化为 n * (n - 1) * (n - 2) / 6。此变量表示满足 1 ≤ i < j < k ≤ N 的三元组 (i, j, k) 的总数。
3. 然后，我们必须初始化一个向量 'sz'。向量的大小为 n。我们必须将向量的所有元素初始化为 1。借助此向量，我们可以存储每个顶点处根子树的大小。
4. 然后，我们必须创建一个递归函数 'dfs'，它有两个参数 'v'（当前顶点）和 'pre'（父顶点）。此递归函数的主要目的是计算每个顶点处根子树的大小，然后相应地更新 'ans' 变量。
5. 然后，在函数内部，我们必须遍历 'v' 的相邻顶点（不包括父顶点 'pre'）。然后我们必须在 'dfs' 函数内部递归调用此函数，将 'c' 作为当前顶点，'v' 作为父顶点。
6. 然后我们必须计算 'sum1' 和 'sum2' 值。然后，我们必须相应地更新 'sz' 向量。
7. 然后我们必须将 'ans' 减去 (sum1 * sum1 - sum2) >> 1。借助这些步骤，我们可以移除在树中形成包含所有三个顶点 i, j 和 k 的简单路径的三元组 (i, j, k)。
8. 然后，我们必须调用 'dfs' 函数，起始顶点为 0，父顶点为 -1。
9. 完成上述所有步骤后，我们必须打印 'ans' 值。这表示满足条件（在树中不包含所有三个顶点 i, j 和 k 的简单路径）的三元组 (i, j, k) 的数量。

让我们借助编程语言实现这些步骤.

C++ 中的实现

输出

说明

在上述程序中，我们实现了一个方法，用于计算每个顶点处根子树的大小。此代码使用 C++ 编程语言实现。

Java 实现

输出

说明

在上述程序中，我们实现了一个方法，用于计算每个顶点处根子树的大小。此代码使用 Java 编程语言实现。

时间复杂度

上述方法的时间复杂度为 O(N)。

空间复杂度

上述方法的空间复杂度为 O(N)。