P7393 「TOCO Round 1」Eternal Star 题解

Cuiyi_SAI · 2024-02-05 00:03:24 · 题解

神仙题。

\large{\text{Solution}}

考虑构造一棵在根节点处取得最大点权 k 且符合要求的树。对于根节点，能够让我们限制它的大小的，只有其子节点的点权和数量。因此我们调整子节点的这些信息就可使得根节点满足要求。

需要限制如下：

• 子节点的点权，肯定包含了 1\cdots k-1。

  若子节点中没有权值为 p 的，那么让根节点变为 p 则可使得整棵树的最大值变成 k-1 且不会产生矛盾，与我们的期望不符。

• 每种权值对应的子节点有多个。

  若没有这层限制，我们当然可以没有顾虑的使得根节点变为 p，而原本权值为 p 的子节点变为 p+1，根节点因此变小了（称这一些列操作为 C，下面将会用到）。但是题目中有着 "点权和最小" 这一要求，于是我们可以通过调整各种子节点的数量来规避这种情况。

  具体的，我们设点权为 p 的子节点的个数为 x，那么为了保持根节点大小不变，应该有 k+px<p+(p+1)x，化简得到 x>k-p。

  综上，第 p 种子节点至少要有 k-p+1 个。为了使点数最少，我们取等。

通过以上方式建立子节点，即可确定一个值为 k 的根节点，对于每棵子树则是子问题，递归处理即可。

该方法实际得分 55pts，错误的原因是建树所使用的节点过多。

优化

为了通过此题，我们需要让所用的总结点数更小，也就需要优化以上建树过程。

观察上述思路，貌似无懈可击，但是我们应该注意到特殊的第 k-1 号子节点。若我们对 k-1 节点进行限制二中的替换（即操作 C），那么实际上其实就是根节点 k 和 k-1 对调了一下——k 依旧是整棵树中最大的节点且依旧可以成为根节点，无事发生，这个操作没有直接的影响答案。

也就是说，对调 k-1 和 k 没有我们想得那么严重，我们只需要使得 k-1 下的子节点可以同样限制住 k 即可保证答案。但是根据限制二得到的不等式，我们却建立了两个 k-1 子节点，这就是一种浪费！

具体的，如果使用这个优化，我们要在原本的 k-1 号子节点下按照对 k 的限制方法，建立编号为 1\cdots k-2 的子树（这是为了让这个位置既能限制 k-1 也能限制 k，也就无惧操作 C），然后删掉多余的那棵 k-1 子树。也就是说我们可以用根为 1\cdots k-2 的这些子树来换掉一棵根为 k-1 的子树。这显然是值得的，因为后者的大小远大于前者，这么一换总结点数就变小了。

将上述优化具象化，我们建树的方式变为：建立两棵对称的树，将其根连接，使得其左右两个根下的 1\cdots k-2 个子节点能够满足对 k 的限制。

至此，本题结束。

\large{\text{Code}}

实现上有一个细节，就是在递归处理子树的时候不能再使用上文的优化。因为用了优化后建的树的对称性，其最大值可以在两个根的位置变化（我们最终答案不关心最大值的位置所以可以使用，但是递归到子树的时候我们有必要做这个限制），这就会导致我们对祖先的限制都失效。因此优化只能在最开始使用。

#include <bits/stdc++.h>
using namespace std;
int K,x,n=0,tot;
pair<int,int> ans[1000010];
int solve(int k,int op){
    int u=++n;
    if(k==1) return u;
    if(u==1) ans[++tot]=make_pair(u,solve(k-1,1));
    for(int i=1;i<k-(u==1);i++){
        for(int j=1;j<=k-i+1+op;j++){
            ans[++tot]=make_pair(u,solve(i,0));
        }
    }
    return u;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>K>>x;
    solve(K,0);
    cout<<n<<'\n';
    for(int i=1;i<=tot;i++) 
        cout<<ans[i].first<<' '<<ans[i].second<<'\n';
    return 0;
}