标签为 [] 的文章

BZOJ2599 Race(点分治)

题目大意 给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小。 Solution 如果我们能知道这棵树里的任意一棵子树,我们一定可以用${size}log_{size}$的复杂度(size表示子树大小)计算出这棵子树内通过根的所以符合条件的路径。具体实现枚举这个根的每棵子树,用map维护一下就好了。(map大法好)。 用分治的思想,计算完整棵树后,把它分成若干棵相同结构的子树,再计算答案。所以只要能找到一个合适的分治点,就可以得到较好的复杂度。 具体实现时,可以找到整棵树的重心,把它作为根,并将它作为分治点继续分治。 因为 ......

BZOJ3626 LCA

题目大意 给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1 设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先 有q次询问,每次询问给出l r z,求$\sum_{i=l}^{r}deep[LCA(i,z)]$ 题解 做这题,首先要发现一个事实:两个点的LCA的深度就是两个点分别到根的链的公共点 所以,对于一次询问,可以将[l,r]区间内的点到根的链的每一个的权值+1,答案即为z到根的链上的点的权值和 这个是可以用树链剖分维护的 对于多次询问,我们将一个询问变成[1,l-1]和[1,r]两个询问,将询问排序,一边更新 ......

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