100 + 60 + 40 + 30,rk 17.

昨天的 CSP 由于太逆天不补了。

CF gym 102201F Fruit tree

有一棵 $n$ 个节点的树，每个节点上有一个颜色，有 $q$ 次询问，每次询问给定两个点 $u,v$，要求你求出是否有一种颜色在 $u,v$ 的简单路径上出现超过一半次数。

$n,q \leq 2.5 \times 10^5$

P3354 [IOI2005]Riv 河流

Byteland 国，有 $n$ 个伐木的村庄，这些村庄都座落在河边。目前在 Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。木料被砍下后，顺着河流而被运到 Bytetown 的伐木场。

Byteland 的国王决定，为了减少运输木料的费用，再额外地建造 $k$ 个伐木场。这 $k$ 个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到 Bytetown 了，它们可以在运输过程中第一个碰到的新伐木场被处理。显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。

注：所有的河流都不会分叉，形成一棵树，根结点是 Bytetown。

国王的大臣计算出了每个村子每年要产多少木料，你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为：每一吨木料每千米 $1$ 分钱。

$2\le n\le 100$，$1\le k\le \min(n,50)$

2021.2.3 训练赛
赛时通过：A C F G J K
总体感觉打的比较捞，D是一个比较厉害的 DP

P2700 逐个击破

一棵树上有 $k$ 个关键点，要求用最小的代价把这些点划分到不s同连通块中。

$2 \leq k \leq n \leq 10^5$

值得复习

P2458 [SDOI2006]保安站岗

有一棵无根树有 $n$ 个点，每个点都可以被其相邻的点望到。

每个点带有一个权值，求保证所有点都可以被望到的情况下花费总代价最少。

CF1336A/CF1337C

有一个有 $n$ 个点的树，以 1 为根，你可以选择 $k$ 个节点，使得这 $k$ 个节点到 1 节点的最短路径中经过的非选择的点最多。