当前位置: 首页 > news >正文

D. Paths on the Tree

Problem - 1746D - Codeforces

思路:先分析一下题意,根据第一条性质,每次只能够从1开始,而第二条性质则表明对于每个节点来说,经过这个节点的子节点的路径条数应该尽量均衡,最大值与最小值相差不能超过1,所以我们考虑,如果当前要选择k个路径,而当前节点有cnt个子节点,那么每个子节点应该至少经过k/cnt个,同时有k%cnt个需要经过k/cnt+1个,那么我们发现这个问题可以递归的解决,那么我们可以考虑用树形dp,我们将f[i][0]表示以i为根,并且经过ki个,f[i][1]表示以i为根并且经过ki+1个,那么对于叶子节点来说,f[i][0]=cost[i]*k,f[i][1]=cost[i]*(k+1),而对于非叶子节点来说,因为所有的子节点都至少经过ki个,所有我们先将所有子节点的f[j][0]求和为sum,令f[i][0]=f[i][1]=sum,那么我们还要再经过k%cnt个,那么我们就是挑几个子节点,然后让他变为f[j][1],那么我们可以将所有f[j][1]-f[j][0]排个序,按照降序排序,那么我们只需要将差值加上,就相当于这个变为了f[j][1],所以我们只需要求一下前k%cnt的和即可,这是对于f[i][0]来说,而对于f[i][1]来说,则还要多出来一次,那么我们只需要求和倒k%cnt+1即可,并且k%cnt+1按照相同的方法取最大的k%cnt+1个一定也是正确的,因为k%cnt最大为cnt-1个,加一为cnt个,正好等于子节点的个数,所以一定是合法的取法

// Problem: D. Paths on the Tree
// Contest: Codeforces - Codeforces Global Round 23
// URL: https://codeforces.com/problemset/problem/1746/D
// Memory Limit: 256 MB
// Time Limit: 3000 m#include<bits/stdc++.h>
#include<sstream>
#include<cassert>
#define fi first
#define se second
#define i128 __int128
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
const double eps=1e-7;
const int N=5e5+7 ,M=5e5+7, INF=0x3f3f3f3f,mod=1e9+7,mod1=998244353;
const long long int llINF=0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=(ll)x*10+c-'0';c=getchar();} return x*f;}
inline void write(ll x) {if(x < 0) {putchar('-'); x = -x;}if(x >= 10) write(x / 10);putchar(x % 10 + '0');}
inline void write(ll x,char ch) {write(x);putchar(ch);}
void stin() {freopen("in_put.txt","r",stdin);freopen("my_out_put.txt","w",stdout);}
bool cmp0(int a,int b) {return a>b;}
template<typename T> T gcd(T a,T b) {return b==0?a:gcd(b,a%b);}
template<typename T> T lcm(T a,T b) {return a*b/gcd(a,b);}
void hack() {printf("\n----------------------------------\n");}int T,hackT;
int n,m,k;
int h[N],e[M],ne[M],idx;
ll f[N][2];
int cost[N];void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void dfs(int u,int k) {f[u][0]=(ll)cost[u]*k;f[u][1]=(ll)cost[u]*(k+1);int cnt=0;for(int i=h[u];i!=-1;i=ne[i]) {int j=e[i];cnt++;}if(!cnt) return ;int a=k/cnt,b=k%cnt;vector<ll> vis;for(int i=h[u];i!=-1;i=ne[i]) {int j=e[i];dfs(j,a);f[u][0]+=f[j][0];f[u][1]+=f[j][0];vis.push_back(f[j][1]-f[j][0]);}sort(vis.begin(),vis.end(),[&](ll &a,ll &b){return a>b;});for(int i=0;i<b;i++) f[u][0]+=vis[i];for(int i=0;i<=b;i++) f[u][1]+=vis[i];
}void solve() {n=read(),k=read();memset(h,-1,sizeof(int)*(n+4));idx=0;for(int i=2;i<=n;i++) {int c=read();add(c,i);}for(int i=1;i<=n;i++) cost[i]=read();dfs(1,k);printf("%lld\n",f[1][0]);
}   int main() {// init();// stin();// ios::sync_with_stdio(false); scanf("%d",&T);// T=1; while(T--) hackT++,solve();return 0;       
}          

相关文章:

D. Paths on the Tree

Problem - 1746D - Codeforces 思路&#xff1a;先分析一下题意&#xff0c;根据第一条性质&#xff0c;每次只能够从1开始&#xff0c;而第二条性质则表明对于每个节点来说&#xff0c;经过这个节点的子节点的路径条数应该尽量均衡&#xff0c;最大值与最小值相差不能超过1&am…...

CocosCreator3.8研究笔记(九)CocosCreator 场景资源的理解

相信很多朋友都想知道&#xff0c; Cocos Creator 资源的定义&#xff1f; Cocos Creator 常见的资源包含哪些&#xff1f;Cocos Creator 资源的管理机制是什么样的&#xff1f; Cocos Creator 中所有继承自 Asset 的类型都统称资源 &#xff0c;例如&#xff1a;Texture2D、Sp…...

大数据课程L1——网站流量项目的概述整体架构

文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 了解网站流量项目的案例概述; ⚪ 了解网站流量项目的数据埋点和采集; ⚪ 了解网站流量项目的整体架构; 一、网站流量项目概述 1. 背景说明 网站流量统计是改进网站服务的重要手段之一…...

提升数据库安全小技巧,使用SSH配合开源DBeaver工具连接数据库

title: 提升数据库安全小技巧&#xff0c;使用SSH配合开源DBeaver工具连接数据库 categories: 独立博客的方方面面 前段时间, 未来降低网址运行成本&#xff0c;搭了一套Mysql Docker 数据库, 包括外部链接&#xff0c;数据备份&#xff0c;数据导出&#xff0c;数据恢复一套解…...

信息安全技术概论-李剑-持续更新

图片和细节来源于 用户 xiejava1018 一.概述 随着计算机网络技术的发展&#xff0c;与时代的变化&#xff0c;计算机病毒也经历了从早期的破坏为主到勒索钱财敲诈经济为主&#xff0c;破坏方式也多种多样&#xff0c;由早期的破坏网络到破坏硬件设备等等 &#xff0c;这也…...

java项目基于 SSM+JSP 的人事管理系统

java项目基于 SSMJSP 的人事管理系统 博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W,Csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 大家好&#xff0c;今天和大家聊的是 Java 基于 SSM 的人事管理系统。…...

【Node.js】—基本知识点总结

【Node.js】—基本知识总结 一、命令行常用操作 二、Node.js注意点 Node.js中不能使用BOM和DOM操作 总结 三、Buffer buffer是一个类似于数组的对象&#xff0c;用于表示固定长度的字节序列buffer的本质是一段内存空间&#xff0c;专门用来处理二进制数据 特点&#xff1a;…...

Leetcode.174 地下城游戏

题目链接 Leetcode.174 地下城游戏 hard 题目描述 恶魔们抓住了公主并将她关在了地下城 d u n g e o n dungeon dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里&#xff0c;他必须穿过地下城并通过对抗恶魔来拯救公…...

python实现adb辅助点击屏幕工具

#!/usr/bin/env python # -*- coding: utf-8 -*-import re import os import time import subprocess import tkinter as tk from tkinter import messagebox from PIL import Image, ImageTk# 设置ADB路径&#xff08;根据你的系统和安装路径进行调整&#xff09; ADB_PATH C…...

智能合约安全分析,针对 ERC777 任意调用合约 Hook 攻击

智能合约安全分析&#xff0c;针对 ERC777 任意调用合约 Hook 攻击 Safful发现了一个有趣的错误&#xff0c;有可能成为一些 DeFi 项目的攻击媒介。这个错误尤其与著名的 ERC777 代币标准有关。此外&#xff0c;它不仅仅是众所周知的黑客中常见的简单的重入问题。 这篇文章对 …...

nodejs 爬虫 axios 异步爬虫 教程 【一】

axios 自定义headers axios.defaults.headers.common["User-Agent"] "Googlebot/2.1 (http://www.google.com/bot.html)"; 运行环境&#xff1a; node &#xff1a;v18 const axios require("axios"); axios.defaults.headers.common["U…...

Swift学习笔记三(Dictionary 篇)

1 Dictionary 概念 字典储存无序的互相关联的同一类型的键和同一类型的值的集合。字典类型的全写方式 Dictionary<Key, Value>&#xff0c;简写方式 [Key: Value]&#xff0c;建议使用简写方式。字典的 key 必须是可哈希的。 2 Dictionary创建 2.1 初始器创建方式 2.2 …...

javax.mail 遇到501 mail from address must be same as authorization user 的問題

使用不同的兩個帳戶发送email时&#xff0c;第一个账户可以发送成功&#xff0c;但到第二个账户的时候就报出了501 mail from address must be same as authorization user的错误。 具体代码如下&#xff1a; import java.util.Date; import java.util.List; import java.util.…...

【Python】网络编程

Socket Socket (简称 套接字)是进程之间通信一个工具&#xff0c;进程之间想要进行网络通信需要socket。Socket负责进程之间的网络数据传输&#xff0c;好比数据的搬运工。 客户端和服务端 2个进程之间通过Socket进行相互通讯&#xff0c;就必须有服务端和客户端 Socket服务…...

客户端开发常用框架

在Unity游戏开发中&#xff0c;客户端常用的框架包括以下几种&#xff1a; 1.Unity的网络框架&#xff1a;Unity自带了网络框架&#xff0c;包括Unity Networking、Unity Matchmaker和Unity Remote等。这些框架可以帮助我们进行游戏的联机对战、排行榜、跨平台等功能的设计和实…...

数据分析综述

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ &#x1f434;作者&#xff1a;秋无之地 &#x1f434;简介&#xff1a;CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作&#xff0c;主要擅长领域有&#xff1a;爬虫、后端、大数据…...

区块链技术与应用 - 学习笔记2【密码学基础】

大家好&#xff0c;我是比特桃。本系列笔记只专注于探讨研究区块链技术原理&#xff0c;不做其他违反相关规定的讨论。 区块链技术已被纳入国家十四五规划&#xff0c;在“加快数字发展 建设数字中国”篇章中&#xff0c;区块链被列为“十四五”七大数字经济重点产业之一&#…...

制作Linux发行版安装镜像:复刻centos镜像安装ISO

制作Linux发行版安装镜像&#xff1a;复刻centos镜像安装ISO 我们平时经常下载Linux各个发行版&#xff0c;下载ISO&#xff0c;安装使用。那么ISO到底是如何制作的&#xff1f;安装过程是什么原理&#xff1f; 近来打算讲镜像制作的过程、原理&#xff0c;通过一个专栏分享一…...

【复习socket】每天40min,我们一起用70天稳扎稳打学完《JavaEE初阶》——29/70 第二十九天

专注 效率 记忆 预习 笔记 复习 做题 欢迎观看我的博客,如有问题交流,欢迎评论区留言,一定尽快回复!(大家可以去看我的专栏,是所有文章的目录)   文章字体风格: 红色文字表示:重难点★✔ 蓝色文字表示:思路以及想法★✔   如果大家觉得有帮助的话,感谢大家帮忙 点…...

postgresql-常用数学函数

postgresql-常用数学函数 案例 案例 --求余 1 select 5%2 as t; --绝对值 17.4 select abs(-17.4) as t2; -- 大于等于最小整数 -42 select ceil(-42.8) as t3; -- 小于等于的最大整数 42 select floor(42.3) as t4; -- 四舍五入 44 select round(43.6) as t5; -- 向零取整 12…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...