标签为 [虚树] 的文章

BZOJ3572 [Hnoi2014]世界树

题目大意 一棵树,边权为1。次询问。 每次给出个关键点,树上的每一个点被离它最近的关键点管理,如果两个关键点和它距离相等,那么取序号小的那个关键点。 问每个关键点管理多少点。 $ n, q \leq 300000, \sum{m} \leq 300000 $ 题解 建完虚树后跑DP算出每个关键点被哪个点管理以及距离。 然后对虚树中的每条边计算答案,以及计算不再虚树中的点的答案。 代码 C++ #include <cstdio> #include <cstring> #include <algorithm> const int INF = 1e9; int n, m; int x[8000 ......

BZOJ2286 消耗战

题目大意 给定一棵带边权的树,有q次询问,每次给定m个关键点,要求删掉一些边,使得根不与任何关键点连通。 题解 咳咳 只要会虚树,这就是一道裸题。 我这种蒟蒻也只会写裸题了。。。 对每次询问建一遍虚树,然后在虚树上跑DP。 代码 C++ #include <cstdio> #include <algorithm> #include <cstring> const long long INF = 1e18; int edgenum; int vet[600000], val[600000], nextx[600000], head[300000]; int fa[300000][22]; long long f[300000]; int cnt; int ......