做了 NOI2018 归程 学到的东西。

THUPC2022 A.最小公倍树

给定一个点编号在 $[L,R]$ 范围内的完全图，边 $(u,v)$ 的权值为 $\mathrm{lcm}(u, v)$，请你求出这张图的最小生成树权值和。

$L,R \leq 10^6,R - L \leq 10^5$

CF1039D You Are Given a Tree

有一棵 $n$ 个节点的树。

其中一个简单路径的集合被称为 $k$ 合法当且仅当：

树的每个节点至多属于其中一条路径，且每条路径恰好包含 $k$ 个点。

对于 $k\in [1,n]$，求出 $k$ 合法路径集合的最多路径数
即：设 $k$ 合法路径集合为 $S$，求最大的 $|S|$。

$n \leq 10^5$

CF601E A Museum Robbery

最初给定 $n$ 个物品以及背包容量 $k$，有 $q$ 次操作，操作有三种：

• 1 v w 在背包里添加一个体积为 $v$ 价值为 $w$ 的物品
• 2 x 删除编号为 $x$ 的物品
• 3 查询背包总和，以 $\sum\limits_{m=1}^{k}{s(m)*p^{m-1}\ \bmod\ q}$ 的形式输出

$n \leq 5000,k \leq 1000,q \leq 30000$ ，保证操作 $1$ 的个数不超过 $10000$，且至少有一个操作 $3$。

这建图，多是一件美事啊！

CF1638E Colorful Operations

给定一个长度为 $n$ 的序列，初始时所有元素的值为 $0$ ，颜色为 $1$。你需要实现以下三种操作：

• Color l r c ：把 $[l,r]$ 这段的元素颜色改为 $c$
• Add c x：把所有颜色为 $c$ 的元素值都加上 $x$
• Query i：输出元素 $i$ 的值

$n,q \leq 10^6$

CFgym103446I

若⼲物品具有体积 $t_i$ 和价值 $v_i$，选出⾄多 $k$ 件物品 将其体积翻倍，然后选出若⼲物品并将其分为体积和相同的两堆，问选出的物品价值之和最⼤是多少。

$n \leq 100$

周正：“这个题的状态定义是很经典的大家一定要记下来。”

CFgym103409E

Alice 和 Bob 在一个有向图上玩游戏，最开始有向图上没有边，Alice 先手买几条边加到图中，之后，Bob 需要从图中删边直到无边。但是 Bob 每次只能删掉一个边集 $S$ ，$S$ 必须是无环的。

有 $m$ 条边，Alice 最多可以买不超过 $c$ 条边，Alice 想要最大化删边轮数，Bob想要最小化删边轮数，两边都是最聪明的，请求出删边轮数。

$n \leq 2000,m \leq 5000$

分治（英语：Divide and Conquer），字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

From OI-wiki

AGC022E Median Replace

给出一个长度为奇数 $n$ 的残缺 $01$ 串，问有多少种补全方法，每次将连续三个位替换为它们的中位数后，能有一种方案使它变为 $1$。

$n\leq 3\times 10^5$