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：

#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;
}