长剖与贪心+树上反悔贪心:1004T4
长剖的本质是一种贪心。(启发式合并本质也是类似哈夫曼树的过程)
在此题中,首先肯定变直径,然后选端点为根。然后选叶子。而每个叶子为了不重复计算,可以只计算其长剖后所在链的贡献。(本题精髓,用长剖来贪心)
然后钦定某个点必选,就是一种反悔贪心。很显然的思路是删掉排名 2 ∗ k − 1 2*k-1 2∗k−1 的叶子,但考虑:
所以需要考虑离其最近被选的点
#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 500010
//#define M
//#define mo
struct node { int x; long long y, z; };
int n, m, i, j, k, T, p1, p2, in[N];
int u, v, w, qe;
vector<node>G[N]; struct Tree {int i, j, k, rt, mn[N]; long long h[N], mxh[N], mx[N], sum[N]; int son[N], dep[N], top[N]; int f[N][22], rk[N], dfn[N]; node w[N]; void dfs1(int x, int fa, int &p1) {//p1 p2if(h[x]>h[p1]) p1=x; for(auto t : G[x]) {int y=t.y; long long z=t.z; if(y==fa) continue; h[y]=h[x]+z; dfs1(y, x, p1); }}void dfs2(int x, int fa) { //son[x] h[x] dep[x]dep[x]=dep[fa]+1; mx[x]=mxh[x]=h[x]; for(auto t : G[x]) {int y=t.y; long long z=t.z; if(y==fa) continue; h[y]=h[x]+z;
// printf("%lld(%lld) --%lld-> %lld(%lld)\n", x, h[x], z, y, h[y]); dfs2(y, x); mx[x]=max(mx[x], mx[y]); if(mxh[y]>mxh[son[x]]) son[x]=y; }if(son[x]) mxh[x]=mxh[son[x]]; }void dfs3(int x, int fa, int tp) {//top[x] w[x]
// printf("> %d\n", tp); top[x]=tp; f[x][0]=fa; if(in[x]==1 && fa) {w[x].y=h[x]-h[f[top[x]][0]]; w[x].x=x; }for(auto t : G[x]) {int y=t.y; if(y==fa) continue; if(y==son[x]) dfs3(y, x, tp); else dfs3(y, x, y); }}void init() {
// for(i=1; i<=n; ++i) printf("%d ", top[i]); printf("\n");
// for(i=1; i<=n; ++i) printf("%d ", h[i]); printf("\n"); sort(w+1, w+n+1, [] (node x, node y) { return x.y<y.y; }) ; reverse(w+1, w+n+1); for(i=1; i<=n; ++i) {
// printf("%lld(%lld) ", w[i].y, w[i].x); if(w[i].x) sum[i]=w[i].y, rk[w[i].x]=i, dfn[i]=w[i].x; sum[i]+=sum[i-1]; }
// printf("\n"); for(k=1; k<=19; ++k) for(i=1; i<=n; ++i) f[i][k]=f[f[i][k-1]][k-1]; }void dfs4(int x, int fa) {if(in[x]==1 && fa) mn[x]=rk[x]; else mn[x]=1e9; for(auto t : G[x]) {int y=t.y, z=t.z; if(y==fa) continue; dfs4(y, x); mn[x]=min(mn[x], mn[y]); //排名最小 }}int tiao(int x, int g) {for(k=19; k>=0; --k)if(mn[f[x][k]]>g) x=f[x][k]; return f[x][0]; }int lca(int x, int y) {if(x==y) return x; if(dep[x]<dep[y]) swap(x, y); for(int k=19; k>=0; --k)if(dep[f[x][k]]>=dep[y]) x=f[x][k]; if(x==y) return x; for(int k=19; k>=0; --k)if(f[x][k]!=f[y][k]) x=f[x][k], y=f[y][k]; return f[x][0]; }long long calc(int y, int oldy, int newx) {
// printf("Lca(%d %d) : %d\n", oldy, newx, lca(oldy, newx));
// return min(w[mn[y]].y, h[oldy]-h[lca(oldy, newx)]); return min(w[mn[y]].y, h[oldy]-h[y]); }long long que(int x, int k) {if(k==1) {
// int y=dfn[mn[x]]; return h[y]; return mx[x]; }if(mn[x]<=2*k-1) {return sum[min(2*k-1, n)]; }int y=tiao(x, 2*k-1), newx, oldy; long long ans; newx=dfn[mn[x]]; oldy=dfn[mn[y]];
// printf("%d | %d %d %d %d\n", y, newx, oldy, (h[newx]-h[y]), calc(y, oldy, newx)); ans=sum[2*k-1]-calc(y, oldy, newx)+(h[newx]-h[y]); ans=max(ans, sum[2*k-1]-w[2*k-1].y+(h[newx]-h[y])); return ans; }
}T1, T2;void print(long long x) {if(x) print(x/10), putchar(x%10+'0');
}signed main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);freopen("bomb.in", "r", stdin);freopen("bomb.out", "w", stdout);
// T=read();
// while(T--) {
//
// }n=read(); qe=read(); for(i=1; i<n; ++i) {u=read(); v=read(); w=read(); G[u].pb({u, v, w}); G[v].pb({v, u, w}); ++in[u]; ++in[v]; }T1.h[1]=0; T1.dfs1(1, 0, p1); T1.h[p1]=0; T1.dfs1(p1, 0, p2);T1.rt=p1; T2.rt=p2; T1.h[p1]=0; T1.dfs2(p1, 0); T2.h[p2]=0; T2.dfs2(p2, 0);
// printf("%d %d\n", p1, p2); T1.dfs3(p1, 0, p1); T2.dfs3(p2, 0, p2); T1.init(); T2.init(); T1.dfs4(p1, 0); T2.dfs4(p2, 0); while(qe--) {u=read(); k=read(); print(max(T1.que(u, k), T2.que(u, k))); puts(""); }return 0;
}
相关文章:

长剖与贪心+树上反悔贪心:1004T4
长剖的本质是一种贪心。(启发式合并本质也是类似哈夫曼树的过程) 在此题中,首先肯定变直径,然后选端点为根。然后选叶子。而每个叶子为了不重复计算,可以只计算其长剖后所在链的贡献。(本题精髓࿰…...

二叉树经典例题
前言: 本文主要讲解了关于二叉树的简单经典的例题。 因为二叉树的特性,所以关于二叉树的大部分题目,需要利用分治的思想去递归解决问题。 分治思想: 把大问题化简成小问题(根节点、左子树、右子树)&…...

什么是指针的指针和指向函数的指针?
理解指针的指针和指向函数的指针对于C语言初学者来说可能会有些挑战,但它们都是非常重要的概念,可以帮助你更好地理解和利用C语言的强大功能。在本文中,我将详细解释这两个概念,包括它们的概念、用途和示例。 指针的指针…...

多个excel合并
目的:将同一个文件下的多个 “京东差评.xlsx” 合并为一个:“京东汇总.xlsx" 代码如下: # -*- coding: utf-8 -*- """ Created on Wed Oct 4 12:52:32 2023author: 64884 """import pandas as pd impor…...

Integrity Plus for Mac,保障网站链接无忧之选
在如今数字化的时代,网站链接的完整性对于用户体验和搜索引擎排名至关重要。如果您是一位网站管理员或者经常需要检查网站链接的人,那么Integrity Plus for Mac(Integrity Plus)将成为您最好的伙伴。 Integrity Plus是一款专业的…...

C#,数值计算——Sobol拟随机序列的计算方法与源程序
1 文本格式 using System; using System.Collections.Generic; namespace Legalsoft.Truffer { /// <summary> /// Sobol quasi-random sequence /// </summary> public class Sobol { public Sobol() { } public static void sobseq(int n,…...

以太网协议介绍(ARP、UDP、ICMP、IP)
以太网协议介绍 一、ARP协议 请求: 应答: ARP协议: 0x0001 0x0800 6 4硬件类型:2个字节,arp协议不仅能在以太网上运行还能在其他类型的硬件上运行。以太网用1来表示; 协议类型:两字节。指的是a…...

【C++】STL详解(十)—— 用红黑树封装map和set
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:C学习 🎯长路漫漫浩浩,万事皆有期待 上一篇博客:【C】STL…...

Android学习之路(17) Android Adapter详解
Adapter基础讲解 本节引言 从本节开始我们要讲的UI控件都是跟Adapter(适配器)打交道的,了解并学会使用这个Adapter很重要, Adapter是用来帮助填充数据的中间桥梁,简单点说就是:将各种数据以合适的形式显示到view上,提供 给用户看…...

实验室超声波萃取技术的原理和特点是什么?
梵英超声(fanyingsonic)实验室超声波清洗机 超声波萃取中药材的优越性源于超声波的特殊物理性质。通过压电换能器产生的快速机械振动波,超声波可减少目标萃取物与样品基体之间的作用力,从而实现固液萃取分离。 (1)加速介质质点运…...

用Python操作Word文档,看这一篇就对了!
本文主要讲解Python中操作word的思路。 一、Hello,world! 使用win32com需要安装pypiwin32 pip install pypiwin32 推荐使用python的IDLE,交互方便 1、如何新建文档 from win32com.client import Dispatchapp Dispatch(Word.Application…...

力扣 -- 879. 盈利计划(二维费用的背包问题)
解题步骤: 参考代码: 未优化的代码: class Solution { public:int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {//计划数int lengroup.size();//每一维都多开一行空间vector&…...

虚拟机的三种网络连接模式
文章目录 桥接模式NAT模式主机模式 桥接模式 虚拟系统占用主机网段中的一个IP地址,可以正常上网 NAT模式 主机生成一个非本主机的网段的IP的网卡,同时虚拟系统中使用一个该网段的IP地质,网络数据能通过主机的网卡来代理发送出去࿰…...

SQL调优
# 插入数据 页合并 # order by优化 视频教程:34. 进阶-SQL优化-order by优化_哔哩哔哩_bilibili 在创建索引的时候,如果没有设置顺序,是会默认升序的;但phone想要倒序,则需要额外的排序 根据需要,创建联合…...

python写一个开机启动的选项
创建一个Python脚本,以便用户可以选择在开机时启动它,可以使用pyautogui库来创建一个简单的交互式界面,其中用户可以选择是否将程序添加到开机启动项中 import pyautogui import osdef add_to_startup():# 提示用户选择是否要在开机时启动程序…...

1500*A. Boredom(DP)
Problem - 455A - Codeforces Boredom - 洛谷 解析: 首先统计每个数的个数,并且统计出最大值mx。 问题转换为,从1-mx 中选择任意个数字,使其都不相邻,求最大的总和。 开始没有思路,以为直接选取偶数位和奇…...

小程序关键词排名:优化你的应用在搜索中的地位
曾经,我们沉浸在应用商店的浩瀚海洋中,寻找着那个能够满足我们需求的小程序。而今,作为开发者,你的小程序究竟能否在这个无边的数字海洋中引起更多涟漪呢?故事的开始,恰巧就在这个问题的探寻中。让我们携手…...

OpenGLES:3D立方体纹理贴图
效果展示 一.概述 前几篇博文讲解了OpenGLES绘制多种3D图形,并赋予丰富的色彩,但是在这些3D图形绘制过程中,有一点还没有涉及,就是纹理贴图。 今天这篇博文我会用如下六张图片对立方体进行纹理贴图,实现六个面都是贴…...

线程的概述
#include <pthread.h> int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg); 功能:创建一个子线程 参数: -thread:传出参数,线程创建成功后,子线程的ID被写到…...

竞赛选题 机器视觉目标检测 - opencv 深度学习
文章目录 0 前言2 目标检测概念3 目标分类、定位、检测示例4 传统目标检测5 两类目标检测算法5.1 相关研究5.1.1 选择性搜索5.1.2 OverFeat 5.2 基于区域提名的方法5.2.1 R-CNN5.2.2 SPP-net5.2.3 Fast R-CNN 5.3 端到端的方法YOLOSSD 6 人体检测结果7 最后 0 前言 ǵ…...

python绘图系统27:matplotlib中平面坐标、极坐标和三维坐标的所有绘图函数
文章目录 绘图函数列表为DrawType添加这些绘图函数绘图类别跳转坐标系坐标源代码 绘图函数列表 下面整理了几乎所有matplotlib中的绘图函数,及其在不同坐标轴下的表现。 函数类别2Dpolar3D备注imshow图像X❌❌pcolormesh伪彩图[X,Y,]ZX,Y,Z❌plot曲线图x[,y]x[,y]…...

国庆中秋宅家自省: Python在Excel中绘图尝鲜
【一】国庆中秋: 悟 【国庆中秋】双节来临,相信各位有自己度过的方式,而我却以独特的方式度过了一个说出来不怕各位见笑的双节; 双节到来,没有太多惊喜,也没有太多的负面情绪, 只是喜欢独处,静静反省这些年走过的酸甜苦辣;生活中的许多不欢而散,不期而遇…...

计算机中的进制转换
在计算机软件中,经常需要进行进制转换,这包括二进制、八进制、十进制和十六进制之间的转换。以下是一些常见的转换方法: 二进制转十进制:这是最直接的转换,基本上不需要什么特别的算法。你只需要按照二进制的权值进行…...

Oracle统计信息问题排查常用SQL
Oracle统计信息问题排查常用SQL 对表的基本情况分析统计信息收集作业分析最近一次的统计信息收集修改触发统计信息收集的阈值 对表的基本情况分析 是否为临时表: select owner,table_name,temporary from dba_tables where table_namexxx;是否为分区表:…...

css圣杯布局和双飞翼布局
圣杯布局 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice-width, in…...

机器学习笔记 - 深入研究spaCy库及其使用技巧
一、简述 spaCy 是一个用于 Python 中高级自然语言处理的开源库。它专为生产用途而设计,这意味着它不仅功能强大,而且快速高效。spaCy 在学术界和工业界广泛用于各种 NLP 任务,例如标记化、词性标注、命名实体识别等。 安装,这里使用阿里的源。 pip install spacy…...

网站强制跳转至国家反诈中心该怎么办?怎么处理?如何解封?
在互联网环境中,网站安全是非常重要的。然而,在实际操作过程中,不少网站可能因内容问题、技术安全漏洞等原因被迫下线甚至跳转至国家反诈骗中心网址。面对这一严峻问题,我们如何有效解决,让网站恢复运行并解除强制跳转…...

2023年10月4日
服务器 #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);//实例化一个服务器server new QTcpServer(this);//此时,服务器已经成功进入监听状态&…...

MacBook 录制电脑内部声音
MacBook 录制电脑内部声音 老妈喜欢跳广场舞,现在广场舞音频下载都收费了!没办法,只能自己录歌了,外录有杂音大家也都知道,所以就只能采用内录的方式然后再用 Audition 调整一下音量大小。 一、(前置条件&a…...

mysql主从复制和读写分离
在企业应用中,成熟的业务通常数据量都比较大 单台MySQL在安全性、高可用性和高并发方面都无法满足实际的需求 配置多台主从数据库服务器以实现读写分离 所以要做主从服务器,保证安全性 做一写一读服务器,将提升性能 1、什么是读写分离 …...