BZOJ3631 [JLOI2014]松鼠的新家

BZOJ3631

树链剖分or树上差分 这里是树上差分的做法

考虑链上的差分,对于数组f,要对一段区间[a, b]区间+x,即f[a] += x, f[b + 1] -= x;

同理考虑树上差分,类似可得,对a到b路径上的所有点权+x,即f[a] += x, f[b] += x, f[lca(a, b)] -= x,  f[fa[lca(a, b)] -= x; 其中lca(a, b)为a, b的最近公共祖先,fa[x]为x的父节点。

最后只需dfs上传标记即可。 继续阅读BZOJ3631 [JLOI2014]松鼠的新家

BZOJ2588 Spoj 10628. Count on a tree

BZOJ2588

求树上路径上节点权值k小。

可以发现树上两点u,v之间的第k小点权等价于(root <-> u) + (root <-> v) - (root <-> lca(u, v)) - (root <-> father[lca(u, v)])上的第k小点权,其中root为根节点,lca(u, v)为u和v的最近公共祖先,father[lca(u, v)]为lca(u, v)的父节点。

那么可以维护root到所有节点的权值,显然root到某个点x的权值和root到x父节点的权值只有点x这个点权的差别,那么可以用主席树维护这个东西了。

继续阅读BZOJ2588 Spoj 10628. Count on a tree