自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:34:02，当前版本为作者最后更新于2021-10-04 19:50:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

令 $x$ 表示某时刻的叶结点个数。

我们的思路是，当 $x$ 较大的时候用 del 操作删叶子，当 $x$ 较小的时候不进行删叶子操作，直接求出当前的树的答案。

经过一些尝试，可以发现我们最多使用 $2x$ 次操作来得到答案。

我们先来证明一下 $2x$ 次操作是足够的。若当前还剩下 $k$ 次操作，我们需要 $1$ 次操作报告答案，因此剩下 $k-1$ 次操作可用。我们将其全部用于计算答案，那么此时叶子的个数最多为 $\lfloor\frac{k-1}2\rfloor$，若更多的话操作数将不够。也就是说，还剩 $k$ 次操作时，若选择删叶子，则至少删除 $\lfloor\frac{k-1}2\rfloor$ 个叶子。

可以发现：$\sum_{i=1}^{142}\left(\lfloor\frac{k-1}2\rfloor+1\right)\gt 5000$。因此这样是合理的。

于是我们只需要一个能够在 $2x$ 次操作以内求出有 $x$ 个叶子的树的边权和的做法。

令 $\mathrm{dist}(x,y)$ 表示点 $i$ 与 $j$ 的距离，$d_i$ 表示点 $i$ 的度数。

我们直接对每条边计算是没法做的，因为边数太多了。所以一次查询距离我们要得到很多边的信息。

我们尝试使用每个点到根的距离进行计算（之后默认将 $1$ 当做根）。经过一些推导和尝试，可以发现答案就是下面的式子：

$$\sum_{i=2}^n \mathrm dist(1,i)\cdot(2-d_i)$$

我们来证明一下这个东西。

对每条边考虑它被计算了几次。

定义 $S(u)$ 表示 $u$ 子树内的点集，$|S(u)|$ 表示 $S(u)$ 的大小，也就是 $u$ 的子树大小。

对于 $u$ 到它父亲的边，$u$ 子树内的点到根的路径上都包含这条边，因此它被计算的次数是 $\sum_{v\in S(u)}(2-d_v)$。

对于一个非根结点 $u$，它连向儿子的边数就是它的度数减一。而一棵 $n$ 个结点的树（$n\ge 1$）的点数恰好是边数加一。因此我们有 $|S(u)|=\sum_{v\in S(u)}(d_v-1)$。

然后我们再对之前的式子进行转化，可以得到：

$$\sum_{v\in S(u)}(2-d_v)=\sum_{v\in S(u)}1-\sum_{v\in S(u)}(d_v-1)=|S(u)|-(|S(u)|-1)=1 $$

这说明了每条边的贡献恰好计算了 $1$ 次，于是我们用来计算答案的式子是对的。

利用这个式子，我们只需要对 $d_u\neq 2$ 的结点询问到 $1$ 的距离就可以得到答案。

对于一个有 $x$ 个叶子的有根树，它度数为 $2$ 的非根结点一定不在包含这 $x$ 个叶子的虚树上，而包含指定的 $x$ 个点的虚树最多有 $2x-1$ 个点。也就是说，度数不为 $2$ 的非根结点加上根结点以后也不超过 $2x-1$ 个点。由于一些性质，根结点一定在虚树上，而它的贡献是无需计算的，所以我们最坏只需要 $2x-2$ 次 dis 操作就能够得到答案。

标算需要 $2x$ 次操作，我的做法是比标算更优的。

而且并不需要用到 dfn 操作。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int k=142,n,deg[5005];
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)cin>>deg[i];
	while(1){
		int t=0;
		for(int i=2;i<=n;++i)if(deg[i]!=2)++t;
		if(t<k){
			LL ans=0;
			for(int i=2;i<=n;++i)if(deg[i]!=2){
				LL v=0;
				cout<<"dis 1 "<<i<<endl;
				cin>>v;
				ans+=v*(2-deg[i]);
			}
			cout<<"! "<<ans<<endl;
			break;
		}else{
			cout<<"del"<<endl;
			--k;
			cin>>n;
			for(int i=1;i<=n;++i)cin>>deg[i];
		}
	}
	return 0;
}