4069
P4069 题解
简要题意 给定一棵 \(n\) 个点的树，树有边权。 对每个点维护一个集合 \(S_u\)，一开始集合均包含整数 \(123456789123456789\)。 设 \({\rm dis}_{a,b}\) 为树上两点 \(a\)，\(b\) 的距离。 共 \(m\) 次操作，分为如下两种： s t ......
bzoj #4069. [Apio2015] 巴厘岛的雕塑
bzoj #4069 二进制？按位考虑。 或操作而且最小？按位贪心。 从最高位往下贪，记录一个 \(x\) 表示当前最高位确定了哪些位可以为 \(0\) (其中存在为 \(0\) 方案的位上值为 \(1\) ) 考虑 dp 处理对于第 \(t\) 位能否为 \(0\) ： 设计状态：设 \(dp_{ ......
P4069 SDOI2016 游戏
传送门 solution 树剖后一段路径变成了若干链拼起来。自上而下和自下而上分别维护两棵李超线段树，每条链就是一段数轴，提前处理每个点两种方向上的在链内的横坐标。以最近公共祖先为界，把路径分成两段。从一个点向链的顶端跳就是区间加线段。每次跳完要把线段的截距增加一个横坐标偏移量乘上斜率，因为不同链横 ......
luogu P4069 [SDOI2016] 游戏 题解【李超树+树剖】
[TOC] # 题目描述 [P4069 [SDOI2016] 游戏](https://www.luogu.com.cn/problem/P4069) > 一棵树，树上有 $n$ 个节点，最初每个节点上有$1$个数字：$123456789123456789$。有两种操作： $\centerdot$选择 ......
【题解】P4069 [SDOI2016]游戏
题目描述 Alice 和 Bob 在玩一个游戏。 游戏在一棵有 $n$ 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 $123456789123456789$。 有时，Alice 会选择一条从 $s$ 到 $t$ 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 $r$ ......