E. Count Paths
题目
题解:
#include <bits/stdc++.h>#define forn(i, n) for (int i = 0; i < int(n); i++)using namespace std;int n;
vector<int> a;
vector<vector<int>> g;long long ans;
vector<map<int, int>> cnt;void dfs(int v, int p = -1){int bst = -1;for (int u : g[v]) if (u != p){dfs(u, v);if (bst == -1 || cnt[bst].size() < cnt[u].size())bst = u;}for (int u : g[v]) if (u != p && u != bst){for (auto it : cnt[u]){int x = it.first, y = it.second;if (x != a[v]) ans += cnt[bst][x] * 1ll * y;cnt[bst][x] += y;}}if (bst != -1) swap(cnt[bst], cnt[v]);ans += cnt[v][a[v]];cnt[v][a[v]] = 1;
}int main() {cin.tie(0);ios::sync_with_stdio(false);int t;cin >> t;while (t--){int n;cin >> n;a.resize(n);forn(i, n) cin >> a[i];g.assign(n, {});forn(_, n - 1){int v, u;cin >> v >> u;--v, --u;g[v].push_back(u);g[u].push_back(v);}ans = 0;cnt.assign(n, {});dfs(0);cout << ans << '\n';}return 0;
}
相关文章:

E. Count Paths
题目 题解: #include <bits/stdc.h>#define forn(i, n) for (int i 0; i < int(n); i)using namespace std;int n; vector<int> a; vector<vector<int>> g;long long ans; vector<map<int, int>> cnt;void dfs(int v, int …...
集合论(ZFC)之良创关系(Well-Founded Relation)
定义在集合S中的一个二元关系(Binary Relation)记,<,有(S,<)。如果对于集合S的任意非空子集,都存在关系(<)下的最小元素,那么该关系&…...

centos 安装达梦数据库
一、环境准备 1.1、确认操作系统的版本和数据库的版本是否一致 ## 查看系统版本:cat /etc/redhat-release CentOS Linux release 7.5.1804 (Core)1.2、关闭防火墙和Selinux # 查看selinux是不是disabled / enforce cat /etc/selinux/config## 查看防火墙状态 fir…...

《Windows PE》6.4.1 无 DLL远程注入
本节我们将演示如何实现远程注入的两种不同方案。方案一选择远程注入代码和数据,方案二选择远程注入DLL。 本节必须掌握的知识点: 无DLL远程注入 远程注入DLL 6.4.1 无DLL远程注入 实验四十五:无DLL远程注入(C语言实现…...

浙大数据结构:10-排序6 Sort with Swap(0, i)
这道题用了数环的思想,MOOC最后视频中也有相关介绍,思想还是很巧妙的 机翻 1、思想 2、 主函数 先把数据存进来,然后从头开始遍历,如果该位置数不对则anwser,然后遍历整个环,一直加anwser,如…...

基于vue框架的的爱心捐赠物资信息系统85gsu(程序+源码+数据库+调试部署+开发环境)系统界面在最后面。
系统程序文件列表 项目功能:用户,爱心项目,捐赠类型,捐赠,积分兑换,兑换,捐赠名录,捐赠去向 开题报告内容 基于Vue框架的爱心捐赠物资信息系统开题报告 一、研究背景与意义 随着社会的发展和人们生活水平的提高,爱心捐赠活动逐渐成为连接捐赠者与受赠…...
AI对抗AI:如何应对自动化攻击新时代?
在当今这个生成式AI迅猛发展的时代,自动化攻击的威胁日益加剧。 在人工智能浪潮下,如何利用AI对抗AI,从而实现全方位的网络安全防护? 一、AI浪潮下,自动化攻击加剧 AI技术的发展既带来了前所未有的挑战,也…...
【微服务】微服务注册:构建灵活的服务管理机制
目录 引言一、什么是微服务注册?1.1 服务注册中心的作用1.2 服务注册中心的工作原理1.3 示意图 二、常见的微服务注册中心2.1 各注册中心详细对比 三、微服务注册的实现方式3.1 Spring Cloud Netflix Eureka3.2 Consul3.3 Zookeeper3.4 etcd 四、微服务注册的注意事…...
AsyncTask的工作原理和缺陷
AsyncTask的工作原理及其缺陷 AsyncTask是Android平台提供的一个轻量级的异步任务类,它允许开发者在后台线程中执行耗时操作,并在操作完成后将结果回调到主线程以更新UI。AsyncTask内部封装了线程池和Handler机制,简化了多线程编程的复杂性。…...
【React】事件绑定的方式
1. 内联函数绑定 这是最简单直接的方式,即在 JSX 语法中直接传递一个内联函数。这种方式每次渲染时都会创建新的函数实例,可能会导致不必要的性能开销。 class MyComponent extends React.Component {render() {return (<button onClick{() > th…...

Android ImageView scaleType使用
目录 一、src设置图片资源 二、scaleType设置图片缩放类型 三、scaleType具体表现 matrix: fitXY: fitStart: fitCenter: fitEnd: Center: centerCrop: centerInside: 控制ImageView和图片的大小保持一致…...

【PhpSpreadsheet】ThinkPHP5+PhpSpreadsheet实现批量导出数据
目录 前言 一、安装 二、API使用 三、完整实例 四、效果图 前言 为什么使用PhpSpreadsheet? 由于PHPExcel不再维护,所以建议使用PhpSpreadsheet来导出exlcel,但是PhpSpreadsheet由于是个新的类库,所以只支持PHP7.1及以上的版…...

Python剪辑视频
import os from moviepy.editor import VideoFileClipvideo_dir r"E:\学习\视频剪辑" s_video_file "1.mp4" d_video_file "剪辑片段1.mp4" s_video_path os.path.join(video_dir, s_video_file) # 原视频文件路径 d_video_path os.path…...

LabVIEW提高开发效率技巧----高效文件I/O
在LabVIEW开发中,文件I/O操作常常是性能瓶颈之一,特别是处理大数据时,如何高效地存储和读取数据显得尤为重要。本文将详细介绍如何利用TDMS Streaming来实现高效的文件I/O,并结合具体例子说明在实际开发中的应用技巧。 1. 什么是T…...
影刀RPA接口_查询应用主流程参数结构
影刀接口_查询应用主流程参数结构 链接 import requests from time import sleepaccessKeyId"XXX" accessKeySecret"XXX"#1.获取token def get_access_token():url"https://api.yingdao.com/oapi/token/v2/token/create"headers{"Content…...

2d实时数字人聊天语音对话使用案例,对接大模型
参看: https://github.com/wan-h/awesome-digital-human-live2d 电脑环境: ubuntu 1060ti 下载: git clone https://github.com/wan-h/awesome-digital-human-live2d.gitdocker部署; cd awesome-digital-human-live2d docker-compose -f docker-compose-quickStart.ya…...

LeetCode | 69.x的平方根
这道题很适合用二分来解决,算是二门入门的一个练手题吧思想就是首先设置两个指针,一个是0,一个是x,相当于在数轴上划定一个区域 [ 0 , x ]然后计算数轴中间值和我们想要找的值的大小关系,因为数轴是有序的,…...

使用Windows创建一个MFC应用【带界面】
MFC使用教程【对初学者保姆型友好!】 目录 前提条件 1:创建MFC应用程序 2. 项目结构解读 引用 外部依赖项 头文件 源文件 资源文件 文件功能详解 项目的主要流程 步骤2:配置OpenCV 安装OpenCV 包含目录与库文件 步骤3࿱…...
springboot整合lombok
只需要引入lombok依赖 <dependency> <groupId>org.projectlombok</groupId> <artifactId>lombok</artifactId> <version>1.16.18</version></dependency> 然后application.yml配置文件中加上 logging: level: …...

使用Arcgis批量自动出图
操作方法如下: 1 2 3 4 5 6 7 设置好选项,开始打印。 8 生成pdf。 第一步:shp放到数据库中,标注转注记,然后编辑注记,符号样式设置好。准备出图:(转注记时候尽量压盖监测等选最…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...