尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
DeepSeek    LeetCode 3786. 树组的交互代价总和 Java实现
问题描述给定一棵 n 个节点的无向树节点编号 0 到 n-1以及一个长度相同的数组 groupgroup[i] 表示节点 i 的分组标签。两个节点 u 和 v 若 group[u] group[v]则它们属于同一组。交互代价定义为树上两节点之间唯一路径的边数。要求返回所有同组无序节点对的交互代价总和。核心思路边贡献统计法直接枚举所有同组节点对并计算路径长度时间复杂度为 O(n²)对于 n ≤ 10⁵ 会超时。核心转化总代价 每条边被同组节点对经过的次数之和。对于任意一条边若将其从树中移除树会被分成两部分。假设某组在这条边的一侧子树中有 x 个节点该组总共有 k 个节点则该组中路径经过这条边的节点对数量为 x * (k - x)。因此只需一次 DFS统计每个子树中各分组的节点数量累加每条边的贡献即可。Java 实现javaimport java.util.ArrayList;import java.util.List;class Solution {private long totalCost 0;private int[][] counts; // counts[u][g] 以u为根的子树中分组g的节点数private int[] totalInGroup; // 全树中各分组的总节点数private ListListInteger adj;public long interactionCosts(int n, int[][] edges, int[] group) {// 1. 构建邻接表adj new ArrayList();for (int i 0; i n; i) {adj.add(new ArrayList());}for (int[] edge : edges) {adj.get(edge[0]).add(edge[1]);adj.get(edge[1]).add(edge[0]);}// 2. 统计各分组总节点数分组标签范围为 1 到 20totalInGroup new int[21];for (int g : group) {totalInGroup[g];}// 3. DFS 统计子树中各分组节点数并累加边的贡献counts new int[n][21];dfs(0, -1, group);return totalCost;}private void dfs(int u, int p, int[] group) {// 当前节点自身属于其分组counts[u][group[u]] 1;for (int v : adj.get(u)) {if (v p) continue;dfs(v, u, group);// 对每个分组计算边 (u, v) 的贡献for (int g 1; g 20; g) {if (totalInGroup[g] 2) continue; // 该组不足2个节点无有效节点对long inSubtree counts[v][g]; // 子树v中分组g的节点数long outsideSubtree totalInGroup[g] - inSubtree; // 子树外同组节点数// 该组中路径经过这条边的节点对数量 inSubtree * outsideSubtreetotalCost inSubtree * outsideSubtree;}// 将子树v的统计结果合并到ufor (int g 1; g 20; g) {counts[u][g] counts[v][g];}}}}代码说明1. 数据结构counts[u][g] 存储以 u 为根的子树中分组 g 的节点数量totalInGroup[g] 存储全树中分组 g 的节点总数。2. DFS 遍历从根节点 0 开始递归遍历。对于每个子节点 v先递归处理 v 的子树得到 counts[v][g]。3. 边贡献计算对于边 (u, v)counts[v][g] 是边下方子树中分组 g 的节点数totalInGroup[g] - counts[v][g] 是边上方同组节点数。二者的乘积就是该组中路径经过这条边的节点对数量。4. 结果合并将子树的统计结果累加到父节点 counts[u][g] 中。复杂度分析· 时间复杂度O(n × G)其中 G 是不同分组的数量本题中 G ≤ 20实际为 O(20n)· 空间复杂度O(n × G) 用于存储 counts 数组
RELATED

相关推荐

QueryExcel:三分钟搞定Excel海量数据检索的智能工具

QueryExcel:三分钟搞定Excel海量数据检索的智能工具

QueryExcel:三分钟搞定Excel海量数据检索的智能工具 【免费下载链接】QueryExcel 多Excel文件内容查询工具。 项目地址: https://gitcode.com/gh_mirrors/qu/QueryExcel 你是否曾面对成百上千个Excel文件,需要查找某个关键信息却无从下手&#xf…

📅 2026/10/2 2:36:06
数据库中一些常用英文单词含义

数据库中一些常用英文单词含义

Schema schema 通常指“结构定义”。 在数据库里,它可能有几层意思: 数据库里的命名空间 比如 PostgreSQL 里可以有: public.users sales.orders这里 public、sales 就是 schema,用来组织表。 表结构 比如一张 users 表有哪些字段…

📅 2026/11/17 0:58:50
Stable Diffusion服装设计实战:从草图→面料渲染→动态走秀视频的5步闭环工作流

Stable Diffusion服装设计实战:从草图→面料渲染→动态走秀视频的5步闭环工作流

更多请点击: https://kaifayun.com 第一章:Stable Diffusion服装设计实战:从草图→面料渲染→动态走秀视频的5步闭环工作流 核心工作流概览 该闭环工作流将传统服装设计流程深度耦合生成式AI能力,实现端到端可控创作。五个阶段环…

📅 2026/11/3 20:05:49
MORE NEWS

更多资讯

📰

呈贡在哪里学电工证?证书过期了不知道怎么复审延期?考前押题攻略来了

呈贡在哪里学电工证?证书过期了不知道怎么复审延期?考前押题攻略来了 证书过期了不知道怎么复审延期?这个问题我见过太多人犯了,尤其是在呈贡地区,很多人因为不了解政策、找不到正规培训机构,导致证书过期后无法顺利复审,甚至影响了工作和收入。别急,…

📰

渝中电工证培训价格值不值得考?学历不高也能报名!

渝中电工证培训价格值不值得考?学历不高也能报名! 你是不是也担心自己学历不高,怕报不了名?别急,电工证考试其实对学历要求并不高,只要你有相关工作经验或者愿意接受培训,就完全有机会。那现在问题来了:**渝中电工证培训价格值不值得考?**如果你…

📰

高压电工作业干什么用电子证书怎么查学历不高也能报

高压电工作业干什么用电子证书怎么查学历不高也能报 你是不是也担心学历不高报不了高压电工作业证?别急,这篇文章就是为你准备的。现在越来越多的行业要求持证上岗,高压电工证就是其中之一,但很多人不知道高压电工作业干什么用,也担心自己没学历、没经验…

📰

北京市低压电工证办理丢了怎么补办?官方报名入口全在这了

北京市低压电工证办理丢了怎么补办?官方报名入口全在这了 现在找工作,没有低压电工证,连门都进不去。尤其是在北京这样的大城市,建筑、物业、工程单位对特种作业证要求非常严格, 低压电工证…

📰

电工证有几种类型工种 上岗必备这些你必须知道

电工证有几种类型工种 上岗必备这些你必须知道 实操考试心里没底怕挂科?别慌,这是很多准备考电工证的人的共同焦虑。但你必须知道, 电工证有几种类型工种…

📰

无锡电工证报考费用网上查询:学历不高怕报不上名?看这篇就够了

无锡电工证报考费用网上查询:学历不高怕报不上名?看这篇就够了 学历不高怕报不上名?别急,你不是一个人。无锡电工证报考费用网上查询一直是大家关注的焦点,尤其是在备考阶段,很多人都担心自己因为学历问题被拒之门外。但事实上,只要符合报考条件,学历…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬