4018. 树组的交互代价总和 II 🔒
题目描述
给定一个整数 n 和一棵以节点 0 为根的无向树，树中共有 n 个节点，编号从 0 到 n - 1。该树由一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示节点 ui 和节点 vi 之间存在一条无向边。
同时给定一个长度为 n 的整数数组 group，其中 group[i] 表示节点 i 所属的组标签。
- 当且仅当
group[u] == group[v]时，节点u和v属于同一组。 - 两个节点之间的 交互代价 为它们在树中的 最短距离。
返回所有满足 0 <= u < v < n 且 group[u] == group[v] 的节点对 (u, v) 的交互代价之和。
两个节点之间的 最短距离 是连接它们的唯一路径上的边数。
示例 1：
输入： n = 3, edges = [[0,1],[1,2]], group = [1,1,1]
输出： 4
解释：
所有节点都属于组 1。各节点对之间的交互代价为：
- 节点
[0, 1]：1 - 节点
[1, 2]：1 - 节点
[0, 2]：2
因此，总交互代价为 1 + 1 + 2 = 4。
示例 2：
输入： n = 3, edges = [[0,1],[1,2]], group = [3,2,3]
输出： 2
解释：
- 节点 0 和节点 2 属于组 3，它们之间的交互代价为 2。
- 节点 1 属于不同的组，因此无法与其他节点组成符合条件的节点对。
因此，总交互代价为 2。
示例 3：
输入： n = 4, edges = [[0,1],[0,2],[0,3]], group = [1,1,4,4]
输出： 3
解释：
属于相同组的节点及其交互代价如下：
- 组 1：节点
[0, 1]：1 - 组 4：节点
[2, 3]：2
因此，总交互代价为 1 + 2 = 3。
示例 4：
输入： n = 2, edges = [[0,1]], group = [1,2]
输出： 0
解释：
所有节点都属于不同的组，因此不存在符合条件的节点对。总交互代价为 0。
约束：
1 <= n <= 105edges.length == n - 1edges[i] = [ui, vi]0 <= ui, vi <= n - 1group.length == n1 <= group[i] <= n- 输入数据保证
edges表示一棵合法的树。
解法
方法一
1 | |
1 | |
1 | |
1 | |