P10121 『STA - R4』保险丝

zzafanti · 2024-02-02 13:45:15 · 题解

比赛结束前 20 多秒过掉，真刺激

传送门

description

给定一棵大小为 n 的树。

一个点 x 的权值 f(x) 定义为 \sum\limits_{u\in \text{subtree}(x),P(x,u)} \prod\limits_{v\in \text{subtree(u)},P(x,v)} fib_{\text{dgr}_v}。其中 P(x,u) 表示根节点到 v 路径上所有点至叶子结点的最短距离的最小值大于等于 x 到 v 的距离，\text{dgr}_x 表示 x 的度数，fib_i 表示斐波那契数列第 i 项。

对所有 1\leq x\leq n，求出 f(x)。对合数取模。

• n\leq 10^6

solution

观察到 x 子树内一个点 u 是否满足 P(x,u) 在 x 到 u 的链上是单调的。也就是说，如果 P(x,u) 不成立，那么 u 子树内所有点 v 的 P(x,v) 一定也不成立；如果 P(x,u) 成立，那么 x 到 u 链上每个点 v 都满足 P(x,v)。

定义每个点 x 的 len_x 为根到 x 路径上所有点到叶子结点的最短距离的最小值，容易通过 dfs 线性求出所有 len_x。

然后以每个点为根统计这个点的 f(x)：搜索 x 的子树，如果 dis(x,u)>len_u 就不继续往下搜，容易 dp 出来每个点 u 的 \prod\limits_{v\in \text{subtree}(u),P(x,v)} fib_{\text{dgr}_v}，加起来就是 f(x)。

这样我们获得了一个 O(n^2) 的做法。

如果我们代码实现时每次搜索的复杂度只和搜到的点数有关的话，交上去会发现能过 subtask 3，也就是非叶子节点的度数至少为 2。

仔细想一下可以发现，此时 len_x 是不超过 O(\log n) 的，因为如果 len_x 要取到 k，就必须有子树前 k-1 层是满的，而且至少二叉，就要用掉至少 2^{k-1} 个点。

这时我们搜索 x 就相当于搜索一个满的 len_x-1 层的至少二叉的树。容易发现满二叉树是最劣情况，搜索的复杂度不超过 O(\sum\limits_{k\ge 1} \dfrac{n}{2^k} 2^\frac{k}{2})= O(n)。

又因为 fib_2=1，这启发我们把度数为 2 的非叶子节点缩掉（也就是把链缩掉），把限制转化成 subtask 3。

令根节点、度数大于 2 的点和叶子结点为关键点。关键点之间一定是直链相连，可以对每个关键点记录它上面的直链的信息，对每个直链记录它的父亲和向下第一个关键点，并且对关键点建树。

统计 f(x) 时，如果 x 时关键点，可以直接搜索 x 的子树，直链的贡献是平凡的，到搜索末端可以用二分算直链上的贡献；如果 x 不是关键点，就找到它所在直链下方第一个关键点 p，搜索 p 的子树，计算贡献也很平凡。

可以发现，这么做的复杂度是 O(\sum |K(x)|) 的，|K(x)| 表示满足在 x 子树内且满足 P(x,u) 的关键点 u 的数量。

下面证明 O(\sum |K(x)|)\leq O(n)。

考虑 u 的贡献，它能贡献到的 x 一定是往上连续的一段祖先，而且这个贡献范围的大小不超过 u 子树内最近的叶子到 u 的距离。下面证明对于所有关键点，其到其子树内最近叶子的距离之和不超过 O(n)。

按深度从大往小考虑，一个关键点 u_i 一定能对应上一个叶子 l_i，使得 \forall i,j 路径 (u_i,l_i) 和 (u_j,l_j) 不交。而要证明的距离之和是不超过 \sum dis(u_i,l_i) 的，\sum dis(u_i,l_i) 又是不超过 O(n) 的，所以对于所有关键点，其到其子树内最近叶子的距离之和不超过 O(n)。

这样就做完了这个题。

带上二分时间复杂度 O(n\log n)，二分的常数很小。空间复杂度 O(n)。

应该可以使用双指针精细实现把时间复杂度降到 O(n)，但估计比较麻烦。

code

这是我场上实现的二分的代码的核心部分。时间复杂度 O(n\log n)，可以被链卡到上界。添加了几个注释。

using E=long long;
int n;
vector<int> fa,len,sz,dgr,par,nxt,pos;
vector<vector<int>> ver,Ver;
vector<vector<int>> pt;

void dfs1(int u){
  sz[u]=1;
  for(auto p:ver[u]){
    dfs1(p);
    len[u]=min(len[u],len[p]+1);
    sz[u]+=sz[p];
  }
  if(sz[u]==1) len[u]=0;
}

void dfs2(int u,int minx=len[1]){
  minx=min(minx,len[u]);
  len[u]=minx;
  for(auto p:ver[u]){
    dfs2(p,minx);
  }
}

vector<int> now;
void dfs4(int u,int Fa=1){
  if(u==1||dgr[u]>2||sz[u]==1){
    if(u!=1){
      Ver[Fa].emplace_back(u);
    }
    pt[u]=now;
    for(int i=0; i<(int)now.size(); i++){ // 把 u 上方链中的节点放到 pt[u] 里
      int p=now[i];
      nxt[p]=u,par[p]=Fa,pos[p]=i; // 并记录每个链上的点（即非关键点）对应的向下和向上第一个关键点
    }
    Fa=u;
    now.clear();
  }else{
    now.emplace_back(u);
  }
  for(auto p:ver[u]){
    dfs4(p,Fa);
  }
}

vector<E> dp;
E sum;
void dfs3(int u,int dis=0){
  dp[u]=fib[dgr[u]];
  for(auto p:Ver[u]){
    if(dis+pt[p].size()+1<=len[p]){
      dfs3(p,dis+pt[p].size()+1);
      dp[u]=dp[u]*dp[p]%mod;
      sum=(sum+dp[p]*pt[p].size())%mod;
      dp[p]=1;
    }else{ // 二分计算搜索的边界在哪里
      int l=-1,r=(int)pt[p].size()-1;
      while(l<r){
        int mid=(l+r+1)>>1;
        if(dis+mid+1<=len[pt[p][mid]]) l=mid;
        else r=mid-1;
      }
      sum=(sum+l+1)%mod;
    }
  }
  sum=(sum+dp[u])%mod;
}

void dfs5(int u,int dis=0){ // 这个 dfs 用于暴力，AC 100% 的数据没有使用
  dp[u]=fib[dgr[u]];
  for(auto p:ver[u]){
    if(dis+1>len[p]) continue;
    dfs5(p,dis+1);
    dp[u]=dp[u]*dp[p]%mod;
    dp[p]=1;
  }
  sum=sum+dp[u];
  sum%=mod;
}

int main(){
  cin>>n;
  fib.resize(n+1); dgr.resize(n+1); ver.resize(n+1);
  ifib.resize(n+1); fa.resize(n+1); len=vector<int>(n+1,n+1); sz.resize(n+1);
  for(int i=2; i<=n; i++){
    cin>>fa[i];
    dgr[i]++;
    dgr[fa[i]]++,ver[fa[i]].emplace_back(i);
  }

  fib[1]=fib[2]=1;
  for(int i=3; i<=n; i++){
    fib[i]=fib[i-1]+fib[i-2];
    fib[i]%=mod;
  }

  dfs1(1);
  dfs2(1);

  Ver.resize(n+1);
  pt=Ver;
  nxt=par=pos=vector<int>(n+1);
  dfs4(1);

  E ans=0; dp=vector<E>(n+1,1);
  for(int i=1; i<=n; i++){
    if(sz[i]==1){ // 把叶子直接判了
      ans^=1;
      continue;
    }
    sum=0;
    if(i==1||dgr[i]>2){
      dfs3(i,0);
      dp[i]=1;
    }else{
      if(len[nxt[i]]<pt[nxt[i]].size()-pos[i]){
        int l=pos[i],r=(int)pt[nxt[i]].size()-1;
        while(l<r){
          int mid=(l+r+1)>>1;
          if(mid-pos[i]<=len[pt[nxt[i]][mid]]) l=mid;
          else r=mid-1;
        }
        sum=(sum+l-pos[i]+1)%mod;
      }else{
        dfs3(nxt[i],pt[nxt[i]].size()-pos[i]);
        sum=(sum+(pt[nxt[i]].size()-pos[i])*1ll*dp[nxt[i]]%mod)%mod;
        dp[nxt[i]]=1;
      }
    }
    //cerr<<i<<' '<<sum<<endl;
    sum=(sum%mod+mod)%mod;
    ans^=sum;
  }

  cout<<ans<<endl;

  return 0;
}