标签为 [树形DP] 的文章

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 ......