树上DP

好了，又是爆零的一天，恭喜我自己 $\text{score：0 + 0 + 0 = 0 rk：27/27}$ Problem A：小卖部题目描述ysgh 是一名数数大师。 现在小卖部有 $n$ 种商品，第 $i$ 种有 $a_i$ 个，价格为 $b_i$。 ysgh 总共去了 $Q$ 天小卖部，第 $i$ 天他只会购买编号在 $l_i \sim r_i$ 的商品。他的卡里有 $c_i$ 元，因此他只能购买价值和不超过 $c_i$ 元的物品。 ysgh 想要知道有多少种购买物品的方案。由于答案很大，你只需要输出答案对 $1000000007$ 取模后的结果。两种方案被认为是不同的当且仅当存在一种物品，其购买数量不同。 当然，ysgh玩了个小花招，你需要通过上一个询问的答案来推导下一个询问的参数。 数据范围对于所有测试数据，满足 $1 \le n \le 10000, ~ 1 \le Q \le 50000, ~ 1 \le a_i, b_i, c_i \le 1000, 1 \le l’_i, r’_i \le n$ 题解令 $C = 1000$ 首先看得出来可以用生成函数搞，显然答 ...

看题解里有人说这题实在太水 但我连第一步对点分类都不会（虽然分类完后的确不会很难） 我依旧是太菜 好了进入正题 线段树上打 $\text{tag}$，因为它一直复制来复制去，不可能在没棵线段树上都进行修改，就考虑点的共同性质，相同性质的点可以一起修改，那么此时相当于只进行一次 $\text{modify}$ 就行了 可以将点分成五类： 一类点：半覆盖（就是修改时会经过但是不打标记） 二类点：全覆盖，打标记（区间被修改区间完全覆盖，会被访问到，被打标记） 三类点：全覆盖，不打标记（区间被修改区间完全覆盖，但不会被访问到，就是打标记全覆盖节点的子节点，不被打标记） 四类点：访问不到，会被下传标记 五类点：访问不到，不会被下传标记 那么此时方案数转概率，令 $f_u$ 表示节点 $u$ 有被打标记的概率，即 $u$ 有被打标记的线段树占比，那么最终被打标记的节点 $u$ 个数即为 $f_u \times 2^n$（其中 $n$ 表示被修改次数） 但是会发现写四类点的时候还需要知道它祖先有没有被打标记，所以还需要设一个 $g_u$ 表示节点 $u$ 及其祖先被打标记的概率，开始转移 对一类 ...

这题真的是写到心态爆炸。。 一道边分治 + 虚树 前置知识边分治顾名思义，就是选择一条边，类似点分治对所有经过该边的路径进行处理，但与点分治不同的是，边分治可能会被菊花图卡到 $O (n^2)$，故此时需要重构树，将之变为度数不超过三的二叉树 树重构通过建立新的虚点进行重构，但要满足加入的虚点不影响最后答案计算 12345678910111213141516171819void rebuild (int root, int father) { int nf = 0; for (int i = Head[root]; i; i = Link[i].next) { int v = Link[i].to; LL w = Link[i].w; if (v == father) continue; if (! nf) { Insert (root, v, w), Insert (v, root, w); nf = root; } else { int k = ++ m; // 虚点 Insert (nf, k, 0), ...

首先易得方程，且经过变换有 $$\begin{aligned} f_i &= \min\limits_{dist_i - lim_i \le dist_j} \{f_j + (dist_i - dist_j)p_i + q_i\} \\ f_j &= p_idist_j + f_i - dist_ip_i - q_i \end{aligned}​$$ 在一条直线上时，斜率优化可以用普通$CDQ​$分治实现（会不会过于麻烦？），那么对于在树上斜率优化时，考虑点分治 这时就在点分治中运用$CDQ$分治的思想，即使用在当前重心管辖范围内的通向根节点的那一条链上的节点来更新其它节点就好了 注意在分治中的斜率优化时在凸包上加点和更新右侧节点答案要同时进行，不然当前最优解可能会在后面由于斜率被删去，导致答案错误，还有由于下面代码是由深度由小到大处理的，所以是反着维护下凸包，即上凸包 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 ...