\(\color{#000000}{\texttt {CF526G}}\)
先考虑单次询问。
发现 \(y\) 条路径的端点一定是叶子节点，产生的联通块最多会有 \(2y\) 个叶子。
但还是不好做。
考虑一个相似的问题
一棵有根树，选 \(k\) 个点，最大化这 \(k\) 个点到根节点路径的并的大小。
选的点肯定是叶子。
如果 \(k \geq\) 叶子个数，答案肯定是 \(n\) 。
否则定义一个点的贡献为 \(V_i\) 为 \(i\) 到根节点上没被经过的点的个数。
每次选 \(V_i\) 最大的肯定最优。
性质：每个点一定在其长链顶端的父亲所在长链底端的点被选后被选。
那么 \(V_i=dep_i-dep_{fa_{top_i}}\)，直接贪心。
如果有多次询问，考虑优化上述做法的复杂度。
有一个性质，直径的一个端点端点一定会被选中。
不妨以直径端点为根，那么还要选 \(2y-1\) 个叶子。
预处理下即可。
考虑原问题。
若直接用上述做法，可能 \(x\) 不在联通块内。
有两种策略进行调整
发现 \(2\) 策略不是很好维护。
但是如果 \(2\) 策略比 \(1\) 策略优，那么 \(x\) 的祖先中离 \(x\) 最近的被覆盖的点的子树中只能有 \(1\) 个被选中的点。
倍增往上跳即可。
复杂度 \(O((n+q)\log n)\)
原文：https://www.cnblogs.com/Frame233/p/12587814.html