题目大意为作业union tree题解.pdfVIP

Solution

题目大意：

有一棵树，边长为单位长度。每个询问给出m个，每个j

在点a并保护与点a距离不超过r的点，求有多少个点受到保护。

jjj

关键字：树的分治、虚树、可持久化线段树

题解：

每次询问，我们先对的保护范围r进行松弛操作。建出虚树，

j

对于虚树的每一条边上的点，只可能是由边两端的进行保护（因

为进行了松弛操作）。

对于一条边(u,v)（v为靠近根节点的那一端），能轻易求出一个中

间节点w（或者由于奇偶性有两个点，我们暂且只讨论一个），使得

′w

(,)di(w,v)。设w为的父亲，可以发现，此时这条边

r−distuw=r−st

uv

′

上u到w的节点（还包括原树上的细枝末叶，懂的）归u管，w到

v的节点（也包括细枝末叶）归v管。

设F[i[j为原树中离点i距离不超过j的节点数，设G[i[j为原树

]]]]

以i为根的子树中离点i距离不超过j的节点数。

′)

w到v这一段受v保护的节点数=G[v][r]−F[w][r−dist(w,v]

vv

u到w这一段受u保护的节点数=

)

F[u][r]−G[u][r]