问题

给定一棵边带权树，有$MM$人从根节点出发，去各节点拿一把椅子回到根节点。每个人经过一条边需要一定时间，每个节点提供的椅子有数量上限$C_{i}C\_i$，每个节点提供两把椅子的时间至少相差$P_{i}P\_i$。问所有人拿一把椅子回到根节点至少需要多少时间。

题解

本题具有二分性

预处理每个节点$ii$到根的路径长度$le{n}_{i}len\_i$

二分答案$TT$，若节点$ii$满足$2\ast le{n}_i\le T2\; *\; len\_i\; \backslash le\; T$，则其能提供的椅子数量上限为

注意特判$P_i=0P\_i=0$的情况

时间复杂度$O(N\log W)O(N\; \backslash log\; W)$，其中$WW$为答案时间数量级

吐槽

这题的定位是签到，内榜歪外榜更歪，在内榜过了一车的 & 外榜BG都过了好几个的时候这题外榜竟然是0/0！

所以说是题面太长劝退了好多人嘛

感谢TB茶歇的干饭小哥，怒抢J一血，力挽狂澜把内榜给带回来了