洛谷 『STA - R4』保险丝

比赛结束前 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^k)=O(n\log 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;
}