梦熊联盟-省选模拟赛-蒟蒻の题解&分析

· · 个人记录

写在前面

对于一个普及组刚刚一等奖提高组都学不好的蒟蒻，这次的题确实非常难，所以我来在我的博客里分析一下。

话不多说，开始！

T1：

题意翻译

给定一颗 n 个节点的树，和一个特定的节点 k，对于每个节点有三种选择：

1 给答案贡献 m

2 不对答案有贡献，但是打上标记

3 如果与 k 节点距离 \le l，或者有相邻节点被打上标记，那么可以给答案贡献 w

针对每个节点，可以选择三种选择中的一

总共有 q 次询问，对于每次询问，给定一个 l，求出可以达到的最大的答案

部分分

这种**特殊数据**，考虑**贪心**。 只有一次询问，不用考虑 $q$。 $l = n$ 的话，每个车站与 $k$ 的距离都会 $< y$，所以一定满足第 $3$ 种选择的条件。所以每个节点对答案的贡献都是 $max(m, w)$，毕竟 $0$ 一定小于它们。 那么答案就是 $$\sum^n_{i = 1}max(m_i, w_i)$$ 这个部分分比较好拿。