自动搬运

查看原文

来自洛谷，原作者为

	ylch 博观而约取，厚积而薄发 加油！（查看.com域名帖子中的内容，把后缀改成.me即可）

搬运于2025-08-24 23:04:36，当前版本为作者最后更新于2025-08-14 16:34:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

经典的 F 比 E 简单。

看到题目显然发现 $\text{II}$ 类扩展肯定不如 $\text{I}$ 类扩展优。

假设当前结点为 $u$，有一个和它深度相同的兄弟结点记为 $v$，发现在若干 $\text{I}$ 类操作后 $u$ 一定会成为 $v$ 的父亲，此时只需要再来一个 $\text{I}$ 类操作就能把 $v$ 和 $v$ 的子树都变为“可扩展的”。所以显然没必要在之前先来一个 $\text{II}$ 类操作。

发现其实 $\text{II}$ 类扩展根本没用，因为只要利用 $\text{I}$ 类扩展跳到根节点，再 $\text{I}$ 类扩展一次就能覆盖整棵树。题目就是要求从 $z$ 开始，每次向上走 $p$ 步，走多少次能回到根结点。

发现只要预处理出每个结点的深度就能 $O(1)$ 算。

当然答案最后还要加一，因为跳到根节点后还应执行一次 $\text{I}$ 类扩展来把影响扩大到整棵树。

但良心的出题人在样例三中告诉我们一个特殊情况（如图）：当根结点的度为 $1$（只有一棵子树）且倒数第二次跳跃在从根节点到首次分岔的这条链上时可以不用加一，因为走到根结点前这棵子树上的所有点也一定已经被标记过了。

    o
    |
    o
    |
    o
  / | \
 o  o  o
……………

因为用纯数学方法计算，所以还要特判一些奇奇怪怪的边界情况。

$O(n)$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;

int n, k, cnt, dep[maxn];
vector<int> T[maxn];

void dfs(int u, int fa){ // 统计深度
	dep[u] = dep[fa] + 1;
	for(int v : T[u]){
		if(v == fa) continue;
		dfs(v, u);
	}
}

void dfs2(int u, int fa){ // 统计（说过的特殊情况）从根节点到首次分岔的这条链的长度
	int child = 0, nxt = -1;
	for(int v : T[u]){
		if(v == fa) continue;
		child ++; nxt = v;
	}
	if(child > 1 || nxt == -1) return ; // 到分岔了 或 到叶子了，返回
	cnt ++;
	dfs2(nxt, u);
}

void solve()
{
	cin >> n >> k;
	for(int i = 1; i <= n - 1; i ++){
		int u, v; cin >> u >> v;
		T[u].push_back(v), T[v].push_back(u);
	}
	dep[0] = -1; // 根节点层为0，这样计算起来会方便一些
	dfs(k, 0);
	dfs2(k, 0);
	int T; cin >> T;
	while(T --){
		int z, p; cin >> z >> p;
		if(n == 1) cout << "0\n";
		else if(p == 0) cout << "-1\n";
		else if(z == k) cout << "1\n";
		else{
			int t = (dep[z] % p == 0? p : dep[z] % p); // 找倒数第二次时距离根结点的距离，注意特判整除
			if(t > cnt) cout << (dep[z] + p - 1) / p + 1 << '\n'; // ceil(dep[z]/p)+1
			else cout << (dep[z] + p - 1) / p << '\n'; // 否则能省一步
		}
	}
}

signed main()
{
	ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	solve();
	return 0;
}