P7895 的爆标做法

令 $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： ```cpp #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; } ```