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

LGP11189 [KDOI R10] 水杯降温 学习笔记

LGP11189 [KDOI R10] 水杯降温 学习笔记

\(\texttt{Luogu Link}\)

前言

不拖啦。

题意简述

有一棵 \(n\) 个结点的树,以 \(1\) 为根。每个结点 \(u\) 有权值(水杯),初始为 \(a_u\)

你有两种操作,可进行任意次:

  • 加热:子树全体加 \(1\)
  • 吹风:从某叶子到根直链全体减 \(1\)

问能否通过操作使得最后所有权值均为 \(0\)

\(n\le 10^5\)\(a_i\le 10^{12}\)

做法解析

以及分析这整道题的内容,你会发现:有的是两种“区间”改,最终对某种状态的要求;没有的是区间求和,树路径信息;看起来不太有的是树上 \(\texttt{DP}\) 值的维护。这导向树上差分。

对于父子 \((u,v)\),设 \(d_v=a_v-a_u\),特别地定义 \(d_1=a_1\)。在这个视角下,对 \(u\) 子树全体加,相当于把 \(d_u\) 加一;对 \(u\) 到根直链全体减 \(1\),就是对于这直链上所有的结点 \(u\),对于它们所有不在直链上的儿子 \(v\),将 \(d_v\) 加一。

你容易发现,所有 \(d_u\) 的值全都是只增不减的。这样,无解的判定很简单了:终局是要求所有 \(a_u=0\) 的,这相当于要求 \(a_1=0\) 且所有 \(d_u=0\),因此,若存在 \(d_u>0\) 则无解(此处 \(u\neq 1\))。

进行了上面的判断后,那什么时候有解呢?首先如果初始 \(a_1\le 0\) 那就必然有解,因为我们可以先对着 \(1\) 子树加若干次把 \(a_1\) 加到 \(0\),再对着下面所有 \(d_u<0\) 的结点子树加到 \(d_u=0\)。这是简单的。

相对困难的是 \(a_1>0\) 的情形。这意味着我们必须先对着 \(1\) 吹若干次风,把 \(a_1\) 吹到 \(0\),再对着下面所有 \(d_u<0\) 的结点子树加到 \(d_u=0\)。问题在于,我们这些风要对着哪吹呢?吹风会使“很多”的 \(d_u\) 增大,我们不能让 \(d_u\) 被加到大于 \(0\)

于是,我们设 \(f_u\) 表示,只考虑 \(u\) 的子树,对着这个子树内的点最多可以吹风多少次。显然对于 \(f_u\) 来说 \(f_v\) 都是自己的子问题,所以这个东西从可以从下往上转移。

具体来说,我们来考虑一下 \(f_u\) 取值有什么限制。\(f_u\) 条吹风直链经过 \(u\) 时,对于它的一个儿子 \(v\) 来说,若有 \(g_v\) 条吹风直链经过它,就意味着有 \(f_u-g_v\) 条直链从它旁边擦肩而过。由我们之前的分析,这意味着 \(d_v\) 会被加上 \(f_u-g_v\) 次。那么显然我们要求:\(\forall v\in son[u]\)\(f_u-g_v\le |d_v|\),当然还有 \(g_v\le f_v\)。因此总的限制就是:\(f_u-|d_v|\le g_v\le f_v\)\(\sum g_v\le f_u\)\(f_u\le \sum f_v\)

如果你特别糖,你可能会问:为什么 \(f_u\le \sum f_v\)?难道不能从 \(u\) 吹一些风吗?

确实不能。题目说的是“吹风:从某叶子到根直链全体减 \(1\)”。你是不是把“叶子”两个字看掉了。

显然 \(f_u\) 越小条件越好满足,\(f_u\) 是可二分的。所以二分就完了。

代码实现

Inf 只开了 \(10^{13}\) 而非 \(10^{18}\)。原因是我的 fss 是直接加的,如果叶子太多 Inf 又太大可能在二分内或者求 fss 处加爆 long long

#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1e5+5;
const lolo Inf=1e14;
int N,X,tfa[MaxN];
lolo A[MaxN],D[MaxN],F[MaxN],fss[MaxN];
vector<int> Tr[MaxN];
bool check(int u,lolo lim){lolo tsum=0;for(auto v : Tr[u])tsum+=max(0ll,lim-D[v]);return tsum<=lim;
}
void dfs(int u){if(!Tr[u].size()){F[u]=Inf;return;}fss[u]=0;for(int v : Tr[u])dfs(v),fss[u]+=F[v];lolo sl=0,sr=min(Inf,fss[u]),smid,sres=-1;for(auto v : Tr[u])minner(sr,F[v]+D[v]);while(sl<=sr){smid=(sl+sr)>>1;if(check(u,smid))sres=smid,sl=smid+1;else sr=smid-1;}F[u]=sres;
}
void mian(){readi(N);for(int i=1;i<=N;i++)Tr[i].clear();for(int i=2;i<=N;i++)readi(tfa[i]),Tr[tfa[i]].push_back(i);for(int i=1;i<=N;i++)readi(A[i]);for(int i=1;i<=N;i++)D[i]=A[i]-A[tfa[i]];for(int i=2;i<=N;i++)if(D[i]>0){puts("Shuiniao");return;}for(int i=1;i<=N;i++)D[i]=abs(D[i]);if(A[1]<0){puts("Huoyu");return;}dfs(1);puts(F[1]>=A[1]?"Huoyu":"Shuiniao");
}
int Tpn,Tcn;
int main(){readis(Tpn,Tcn);while(Tcn--)mian();return 0;
}
http://www.hskmm.com/?act=detail&tid=30775

相关文章:

  • notepad++中使用正则表达式过滤数据
  • 从孔子到马斯克:理解原理与问对问题的智慧史
  • startPage()分页总数问题
  • 2025 年电感源头厂家最新推荐排行榜:聚焦功率一体成型屏蔽共模等系列,助力企业精准选优质制造商屏蔽/共模/贴片共模/磁环/磁胶SWPA电感厂家推荐
  • 2025 年风机厂家最新推荐排行榜:聚焦交流 / 直流 / 无刷 / 大吸力 / 调速 / 小型高压等多类型风机,精选优质企业助力采购决策
  • 简单高效的SQL注入测试方法:Break Repair技术详解
  • AG Grid推出全新MCP服务器——让AI更智能地理解你的数据表格!
  • 2025 年自动供料系统厂家推荐榜:集中/挤出机/高速混合机/混料机/搅拌机/粉体颗粒/反应釜/SPC自动供料系统厂家,聚焦高效环保,张家港华耐德环保科技引领行业
  • uniapp 判断在特定app或h5里还需要判断当前环境
  • 工业流体输送 “心” 选择!2025 螺杆泵、隔膜泵、磁力泵、自吸泵、计量泵五大靠谱厂家推荐 —— 从研发实力到售后保障的全方位筛选
  • 盘点2025年试验箱十大品牌top,涵盖高低温湿热/小型/步入式/品质好有保障!
  • Excel处理控件Aspose.Cells教程:使用Python将TXT文件转换为CSV
  • 2025 年干燥机厂商最新推荐排行榜:聚焦实验室与工业用优质设备,精选实力品牌供采购参考工业喷雾 / 陶瓷喷雾 / 制粒 / 奶粉喷雾 / 离心喷雾干燥机厂家推荐
  • CF Round 1024 / CF2101
  • 本地 Git 清理已经在远程删除的分支引用
  • 一切皆有逻辑,元推理框架是逻辑真相生成器
  • 2025 年工业减速机厂家最新推荐排行榜:聚焦谐波 / 行星 / 直角换向器等多类型设备,精选实力企业助力采购决策
  • 如何用有限元法,分析物体表面的张力?
  • 2025 年最新切割机厂家口碑推荐排行榜:全包围 / 半包围激光切割机及金属等离子切割机优选企业指南
  • Exp2
  • Hadoop RPC深度解析:分布式通信的核心机制 - 教程
  • 2025 运动鞋品牌推荐:从专业竞速到大众适配的全场景选择
  • 替代FTP文件传输工具有哪些?
  • 国产DevOps工具链崛起:Gitee如何重塑企业研发效能
  • PD快充诱骗电压芯片XSP25支持5V9V10V11V12V15V20V电压
  • electron——屏蔽顶部标题栏最大化按钮 - 前端
  • 2025 年折弯机厂家最新推荐排行榜:涵盖数控 / 电液伺服 / 液压 / 小型等机型,助力企业精准选购优质设备
  • 2025 年国内变压器优质厂家最新推荐排行榜:聚焦低压/单相/三相/特种/定制/非标/配电/节能/光伏/隔离变压器设备,助力用户精准选靠谱品牌
  • 数据安全交换系统是什么?有哪些核心价值?
  • 2025 年流量计厂家最新推荐排行榜:聚焦国内优质厂商,覆盖电磁涡街等多类型产品,助力企业精准选型避开风险液体质量/金属管浮子/液体涡轮/气体涡轮/旋进漩涡/空气流量计厂家推荐