洛谷P1351 [NOIP 2014 提高组] 联合权值

洛谷P1351 [NOIP 2014 提高组] 联合权值

洛谷题目传送门

题目背景

NOIP2014 提高组 D1T2

题目描述

无向连通图 G G G n n n 个点, n − 1 n-1 n1 条边。点从 1 1 1 n n n 依次编号,编号为 i i i 的点的权值为 W i W_i Wi,每条边的长度均为 1 1 1。图上两点 ( u , v ) (u, v) (u,v) 的距离定义为 u u u 点到 v v v 点的最短距离。对于图 G G G 上的点对 ( u , v ) (u, v) (u,v),若它们的距离为 2 2 2,则它们之间会产生 W v × W u W_v \times W_u Wv×Wu 的联合权值。

请问图 G G G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?

输入格式

第一行包含 1 1 1 个整数 n n n

接下来 n − 1 n-1 n1 行,每行包含 2 2 2 个用空格隔开的正整数 u , v u,v u,v,表示编号为 u u u 和编号为 v v v 的点之间有边相连。

最后 1 1 1 行,包含 n n n 个正整数,每两个正整数之间用一个空格隔开,其中第 i i i 个整数表示图 G G G 上编号为 i i i 的点的权值为 W i W_i Wi

输出格式

输出共 1 1 1 行,包含 2 2 2 个整数,之间用一个空格隔开,依次为图 G G G 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大,输出它时要对 10007 10007 10007 取余。

输入输出样例 #1

输入 #1

5  
1 2  
2 3
3 4  
4 5  
1 5 2 3 10

输出 #1

20 74

说明/提示

样例解释

本例输入的图如上所示,距离为 2 2 2 的有序点对有 ( 1 , 3 ) (1,3) (1,3) ( 2 , 4 ) (2,4) (2,4) ( 3 , 1 ) (3,1) (3,1) 、$(3,5) 、 、 (4,2)$ 、$(5,3) $。

其联合权值分别为 2 , 15 , 2 , 20 , 15 , 20 2,15,2,20,15,20 2,15,2,20,15,20。其中最大的是 20 20 20,总和为 74 74 74

数据说明

  • 对于 30 % 30\% 30% 的数据, 1 < n ≤ 100 1 < n \leq 100 1<n100
  • 对于 60 % 60\% 60% 的数据, 1 < n ≤ 2000 1 < n \leq 2000 1<n2000
  • 对于 100 % 100\% 100% 的数据, 1 < n ≤ 2 × 1 0 5 1 < n \leq 2\times 10^5 1<n2×105 0 < W i ≤ 10000 0 < W_i \leq 10000 0<Wi10000

保证一定存在可产生联合权值的有序点对。

思路详解

虽然这个题目说他是一个图,但由n-1条边的连通图可得他是一棵树,思考如何求解出最大值与和。

最大值

首先考虑哪些点可以凑成一个联合点对???由于只要距离为2,那显然对于一个节点 u u u u u u的任意子节点 v v v,都可以和 u u u的其余所有子节点组成联合点对,也可以和 u u u的父亲节点组成点对。那最大值就很显然了:

  1. v v v与其他子节点组合:显然我们只需要找出最大值 d 1 d_{1} d1与次大值 d 2 d_{2} d2组合即可。
  2. v v v u u u的父亲组合:直接找到最大值 d 1 d1 d1 a f a u a_{fa_{u}} afau组合即可。

与上面相同,我们只需要分为两部分求解即可。具体如下:

  1. v v v u u u的父亲组合:令 u u u的所有子节点权值和为 s u m u sum_{u} sumu,则这一部分答案 a n s 2 = s u m u ∗ a f a u ans_{2}=sum_{u}*a_{fa_{u}} ans2=sumuafau
  2. v v v与其他子节点组合:则这一部分的答案为 a n s 3 = ∑ v a v ∗ ( s u m u − a v ) ans_{3}=\sum _{v} a_{v}*(sum_{u}-a_{v}) ans3=vav(sumuav)因为他不能与他自己组合。

但我们发现联合点对是有序的,那我们是否输出 2 ( a n s 2 + a n s 3 ) 2(ans_{2}+ans_{3}) 2(ans2+ans3)呢???虽然这样样例可以过,但我们只能得到0分的好成绩,这是为何?我们发现 a n s 3 ans_{3} ans3其实已经相当于乘过2了,只有 a n s 2 ans_{2} ans2需要乘2。这就是水样例的恶劣影响。

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e5+5,mod=10007;
ll n,a[N];
ll h[N],to[N],ne[N],tot=0;
void add(ll u,ll v){//建边tot++;to[tot]=v;ne[tot]=h[u];h[u]=tot;
}
ll d1[N],d2[N],ans1=0,sum[N],ans2=0,ans3=0;
//d1[u]为u的子节点的最大值,d2[u]为次大值,sum[u]为u的子节点的和。
void dfs(ll u,ll fa){d1[u]=-0x3f3f3f3f;d2[u]=-0x3f3f3f3f;//赋初值sum[u]=0;for(ll i=h[u];i;i=ne[i]){ll v=to[i];if(v==fa)continue;sum[u]=(sum[u]+a[v])%mod;if(a[v]>d1[u]){d2[u]=d1[u];d1[u]=a[v];}//更新最大值else if(a[v]>d2[u]){d2[u]=a[v];}//更新次大值dfs(v,u);}for(ll i=h[u];i;i=ne[i]){//求解ans3ll v=to[i];if(v==fa)continue;ans3=(ans3+a[v]*((sum[u]-a[v]+mod)%mod)%mod)%mod;}ans2=(ans2+sum[u]*a[fa]%mod)%mod;//求解ans2if(d1[u]==-0x3f3f3f3f&&d2[u]==-0x3f3f3f3f)return;//没有子节点,不更新ans1ans1=max(ans1,max(d1[u]*d2[u],d1[u]*a[fa]));
}
int main(){cin>>n;for(ll i=1;i<=n-1;i++){ll x,y;cin>>x>>y;add(x,y);add(y,x);}for(ll i=1;i<=n;i++)cin>>a[i];sum[0]+=a[1];dfs(1,0);cout<<ans1<<' '<<(ans2*2+ans3)%mod;return 0;
}
/*高级样例
5
1 2
1 3
2 4
2 5
1 2 4 6 5
*/

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/diannao/89740.shtml
繁体地址,请注明出处:http://hk.pswp.cn/diannao/89740.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Apache Doris Profile 深度解析:从获取到分析,解锁查询性能优化密码

在 Doris 数据库中&#xff0c;高效的查询性能是数据处理的关键。当我们遇到查询缓慢、资源消耗异常等问题时&#xff0c;Doris 提供的 Profile 工具就如同一位 “性能侦探”&#xff0c;能帮我们抽丝剥茧&#xff0c;找到问题根源。今天&#xff0c;我们就来深入聊聊如何分析 …

系统架构师

硬件&#xff1a; 运算器&#xff1a;1&#xff09;算术运算 加减乘除 2&#xff09;逻辑运算并进行逻辑测试&#xff1a;与或非 组件功能&#xff1a;算术逻辑单元ALU :处理数据 实现对数据的算术运算和逻辑运算 累加寄存器AC 通用寄存器&#xff0c;alu提供工作区 暂存运算结…

Unity HDRP + Azure IoT 工业设备监控系统实例

Unity HDRP Azure IoT 工业设备监控系统实例 下面是一个完整的工业设备监控解决方案&#xff0c;结合Unity HDRP&#xff08;高清渲染管线&#xff09;的高质量可视化与Azure IoT的实时数据处理能力。 系统架构 #mermaid-svg-XJnD6acrBbtbqYHW {font-family:"trebuchet…

(超详细)数据库项目初体验:使用C语言连接数据库完成短地址服务(本地运行版)

数据库项目初体验&#xff1a;使用C语言连接数据库完成短地址服务&#xff08;本地运行版&#xff09; 前言&#xff1a;初学者的思考 作为一个刚初学数据库的小白并且在之前我的博客中我有尝试使用C语言写过一个短地址服务&#xff0c;但是使用C语言编写的短地址服务只有短记…

mysql基础(一)快速上手篇

连接mysql 使用命令行窗口连接mysql数据库 语法&#xff1a;mysql –h主机名 –u用户名 –p密码 说明&#xff1a;-h参数指定数据库ip&#xff0c;本地服务器可以用localhost&#xff0c;-u参数指定用户名&#xff0c;-p参数指定用户密码。 注意&#xff1a;-p和密码值之间…

IntelliJ IDEA 2025- 下载安装教程图文版详细教程(附激活码)

目录 写在前面 一、介绍 二、下载 三、安装 &#x1f3c1; 写在最后 写在前面 > &#x1f680; 初学 Java&#xff1f;或者刚开始写项目&#xff0c;不知道该选哪个 IDE&#xff1f; 本篇教程手把手教你安装 IntelliJ IDEA —— JetBrains 出品的顶级 Java 开发环境&a…

数学经济专业大学四年规划

数学经济专业结合了数学的逻辑严谨性和经济学的现实应用性&#xff0c;为学生提供了强大的数理分析能力和经济洞察力。该专业毕业生在金融科技、量化投资、商业分析等领域具有显著优势&#xff0c;尤其在数字经济时代&#xff0c;这类复合型人才的需求量持续增长。一、数学经济…

局域网打印机共享怎么设置?如何配置内网本地网络打印机给异地电脑远程连接使用打印?

打印机共享怎么设置&#xff1f;如何设置本地内网的网络打印机共享给其他网络下电脑连接打印&#xff1f;打印机设置使用以及异地使用打印都是大家比较关注的问题&#xff0c;下面详细教程中分二步&#xff0c;先讲局域网内的打印机共享&#xff0c;再进一步介绍内网打印机地址…

Rust异步爬虫实现与优化

Rust 语言在爬虫领域的应用相对较少&#xff0c;尽管 Rust 的 async/await 已稳定&#xff0c;但其与线程安全、Pin 等概念的结合仍较复杂&#xff0c;而爬虫高度依赖并发处理&#xff0c;进一步提高了开发成本。这就导致了使用Rust语言爬虫用的人很少。 下面是一个使用 Rust 编…

Electron 安全最佳实践:构建安全的桌面应用

Electron 是一个流行的框架&#xff0c;允许开发者使用 Web 技术&#xff08;HTML、CSS、JavaScript&#xff09;构建跨平台桌面应用。许多知名应用&#xff0c;如 VS Code、Slack 和 Discord&#xff0c;都基于 Electron 开发。然而&#xff0c;由于其结合了 Node.js&#xff…

MySQL 事务详解:从基础操作到隔离级别与 MVCC 原理

前言 首先从概念上进行理解什么是事务&#xff0c;以及事务的4大属性&#xff0c;知道是什么还要知道为什么&#xff1f; 事务是如何进行操作的&#xff0c;最后在谈事务的隔离性、隔离级别&#xff08;最重要但是也很难理解&#xff09;&#xff0c;理解隔离级别体现在哪里 …

【Unity 编辑器工具开发:GUILayout 与 EditorGUILayout 对比分析】

Unity 编辑器工具开发&#xff1a;GUILayout 与 EditorGUILayout 对比分析 一、核心区别对比 方面GUILayoutEditorGUILayout区别命名空间UnityEngineUnityEditorEditorGUILayout 仅限编辑器环境适用范围游戏运行时 编辑器工具仅限编辑器工具运行时禁用 EditorGUILayout渲染管…

[附源码+数据库+毕业论文]基于Spring+MyBatis+MySQL+Maven+jsp实现的个人财务管理系统,推荐!

摘 要 随着软件信息技术的兴起&#xff0c;许多手工作业也升级为软件管理数据&#xff0c;本次针对个人财务数据的管理&#xff0c;开发一款个人财务管理系统&#xff0c;该系统可以解决许多信息管理上面的难题&#xff0c;比如处理数据时间很长&#xff0c;数据存在错误不能及…

Compose入门3 - 高仿小红书 界面

使用compose 实现一个小红书UI 界面&#xff0c;主要是为了锻炼 使用compose布局的能力 demo地址&#xff1a;https://github.com/PangHaHa12138/ComposeDemo 先上demo 截图 下面是完整的compose代码 package com.example.test001import android.annotation.SuppressLint imp…

mybatis-plus json字段使用typeHandler自动转换为List

mybatis-plus json字段使用typeHandler自动转换为List mybatis-plus json字段使用typeHandler自动转换为List 一、实现思路 1.配置mybatis配置&#xff0c;注入handlermybatis-plus:typeHandlersPackage: com.power.common.core.handler 2.字段顶部增加注解TableField(typeHand…

(C++)学生管理系统(测试2版)(map数组的应用)(string应用)(引用)(C++教学)(C++项目)

1. 头文件与命名空间 #include <iostream> // 输入输出流库&#xff0c;提供cin/cout等基本I/O功能 #include <map> // 映射容器库&#xff0c;提供map数据结构&#xff08;键值对集合&#xff09; #include <string> // 字符串库&#xff0c;…

使用assembly解决jar包超大,实现依赖包、前端资源外置部署

成果物需要部署到用户内网的童鞋应该都遇到过该问题&#xff1a;引入的maven依赖越来越多&#xff0c;jar包越来越大&#xff0c;我之间甚至见过一两个G的依赖&#xff0c;想改个代码换到现场测试&#xff0c;包传到现场要一二十分钟&#xff0c;真正实现了改代码两分钟分钟&am…

基于PHP+MySQL实现(Web)英语学习与测试平台

数据库课设&#xff1a;英语学习与测试平台 运行环境要求 PHP7.1 基于 thinkPHP6.0、Layui、Xadmin 开发 主要功能 公共模块 登录注册个人信息修改密码修改 教师模块 文章查看发布班级管理测试查看发布批改历史成绩查看 学生模块 文章查看参与测试查看成绩 管理员模块…

WinForm中Settings.settings和app.config修改后信息不同步到exe.config问题

在 WinForms 项目中&#xff0c;Settings.settings 和 app.config/exe.config 的关系确实容易让人困惑。以下是问题的根本原因和解决方案&#xff1a; 问题本质 设计时文件&#xff1a;app.config&#xff08;源码中的配置文件&#xff09;运行时文件&#xff1a;bin/Debug/Yo…

【公司环境下发布个人NPM包完整教程】

&#x1f3e2; 公司环境下发布个人NPM包完整教程 创建时间: 2025年7月2日 适用场景: 公司电脑&#xff0c;需要临时切换个人账户发布npm包 &#x1f3af; 教程概述 场景说明 环境: 公司电脑&#xff0c;已配置公司npm账户目标: 临时使用个人账户发布npm包&#xff0c;发布后恢复…