BZOJ3572 [Hnoi2014]世界树

题目大意 一棵树,边权为1。次询问。 每次给出个关键点,树上的每一个点被离它最近的关键点管理,如果两个关键点和它距离相等,那么取序号小的那个关键点。 问每个关键点管理多少点。 $ n, q \leq 300000, \sum{m} \leq 300000 $ 题解 建完虚树后跑DP算出每个关键点被哪 …

题目大意 给定一棵带边权的树,有q次询问,每次给定m个关键点,要求删掉一些边,使得根不与任何关键点连通。 题解 咳咳 只要会虚树,这就是一道裸题。 我这种蒟蒻也只会写裸题了。。。 对每次询问建一遍虚树,然后在虚树上跑DP。 代码 #include <cstdio> #include …