Oql's Blog

发表于 分类于

题意

一棵有根树，树上每个节点有 $a_i$ 个苹果。$m$ 个摄像机，每个摄像机可以看到 $x_i$ 的子树中所有与 $x_i$ 距离不超过 $k_i$ 的点中的苹果，可以花钱 $c_i$ 使该摄像机失效。求最终没有被看到的苹果数 - 花费的钱的最大值。

$n,m\leq 3\times 10^5$ , $\sum n,\sum m\leq 10^6$

阅读全文 »

发表于 分类于

题意

一棵树，求所有三个不同的点，两两距离相同的方案数。

$n\leq 5000$

加强版：$n\leq 10^5$

阅读全文 »

发表于 分类于

题意

一棵有根树，定义 $d_{u,i}$ 表示以 $u$ 为根的子树内离 $u$ 的距离为 $i$ 的节点个数。

对于每个节点 $u$，求出使 $d_{u,j}$ 最大的 $j$，且 $j$ 的编号最小。

$n\leq 10^6$

阅读全文 »

发表于 分类于

题意

一个长度为 $n$ 的序列，对于每个前缀，求最多 $5$ 个互不相交的不下降子序列的元素和的最大值。

$n\leq 10^5,a_i\in[1,10^9]$

阅读全文 »