[CCO2025] Tree Decorations 题解

· · 题解

自己想到的神秘做法。下文中规定 T_u 表示 T 中以 u 为根的子树，d_u 表示 u 在 T 中的深度（认为 d_1=0）。

转换一下题意，可以转为判断有多少种子树 T_r(1\le r\le n)（即两个同构的子树算一种）满足它的子树中所有结点的子树都在 T 中出现了一次，并且将这些出现的子树全部标记出来后，它们之间两两不交。

假设 M 可以为任意值，尝试判断怎样的 T_r 合法。先推一些必要条件，考虑结点 r：令 d'_u 为结点 u(u\in T_r) 在 T_r 中的深度（认为 d'_r=0）。对于一个 u(u\in T_r)，它在 T_r 中的所有祖先的子树必然要在 T 中各出现一次（出现位置不交），于是 T_u 在 T 中也需要出现 d'_u+1 次（如果这个条件不满足那么 r 不可能合法）。

记 c_u 表示 T（注意这里是整棵树）中有多少个 v（u,v 可以相同）满足 T_u 与 T_v 同构，显然该 T_r 可以成为答案当且仅当 \forall u\in T_r 均满足如下条件：

于是就可以提出一个 O(N^2) 做法：枚举 r，先计算出所有 d' 的值，再对于 T_r 内的每“一种”子树检查是否满足上面的条件即可。判断树同构有很多方法，例如 AHU、树哈希（这里我使用的是一种 map 套 vector 的确定性做法，哈希值的值域是 O(N) 的，方便下面的优化），能轻松做到 O(N\log N) 或 O(N)，在此不多赘述。这个做法可以获得 68\% 的分数（M=1 根结点是唯一确定的，时间复杂度少个 N，故可通过子任务 3）。

发现对于一个子树考察其中所有点是否满足条件有点困难，尝试反过来做，对于一个结点 u，考虑它能让哪些祖先因为它而不合法——考察根结点到它的路径 p=\{p_1(=1),p_2,\ldots,p_{k-1},p_k(=u)\}，能够因为它而不合法的点显然是 p 的一段前缀；由此产生了新的思路：使用倍增找到深度最小的不合法点。

现在的问题在于如何判断一个点 r 是否会因为 u(u\in T_r) 而不合法——找出 r 子树中与 T_u 同构的 T_v 对应的所有 v（u,v 可以相等）在 T（整棵树）中的深度之和（可以对于每个哈希值 v 开一个 vector，按照 dfs 序依次存储所有哈希值为 v 的结点，查询时直接在 u 对应的哈希值 v 的 vector 中二分 T_r 对应的 dfs 序区间，再维护一个前缀和即可求出区间深度和），再假设 r 中与 T_u 同构的 T_v 对应的 v 个数为 w（在上面 vector 的二分时可以顺带求出），将深度之和其减去 w\cdot(d_r-1) 即可得到上面 O(N^2) 做法中 \sum\limits_v(d'_v+1)的值（注意这里是 d'）。将其与 c_u 比较从而判断 T_r 的合法性。

最后考虑 M 的条件，这个时候只需要子树内简单地算个贡献，即可得到它的子树内所有结点的子树大小之和 S，判断 S+M=N 是否成立即可。

时间复杂度 O(N\log^2N)，但是由于本题的特殊性你可以加一大堆的小优化使它的速度变快。本人编写的程序实测在洛谷上单个测试点最大用时为 1.4\mathrm{s}。

代码想清楚了非常好写。放代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,m,k,o=0,id=0; cin>>n>>m,k=__lg(n);
  vector<vector<int> > g(n);
  for(int i=1;i<n;i++){
    int u,v; cin>>u>>v;
    g[--u].emplace_back(--v);
    g[v].emplace_back(u);
  }
  vector f(n,vector<int>(k+1,-1));
  vector<int> d(n),l(n),t(n),e(n,1),h(n);
  vector<ll> es(n);
  map<vector<int>,int> mp;
  auto dfs=[&](auto &&self,int u)->int{
    for(int i=1;i<=k&&~f[u][i-1];i++)
      f[u][i]=f[f[u][i-1]][i-1];
    // 倍增求 2^i 级祖先
    t[l[u]=o++]=u;
    // l 表示 dfs 序
    vector<int> v;
    for(int i:g[u])
      if(i!=f[u][0]){
        f[i][0]=u,d[i]=d[u]+1;
        v.emplace_back(self(self,i)),e[u]+=e[i];
      }
    es[u]=e[u];
    for(int i:g[u])
      if(i!=f[u][0])es[u]+=es[i];
    sort(v.begin(),v.end());
    if(mp.find(v)==mp.end())mp[v]=id++;
    return h[u]=mp[v]; // map 维护树哈希
  };
  dfs(dfs,0); // 预处理所有需要的信息
  vector<vector<int> > dv(n);
  vector<vector<ll> > sv(n);
  for(int u=0;u<n;u++){
    dv[h[t[u]]].emplace_back(u);
    sv[h[t[u]]].emplace_back((sv[h[t[u]]].empty()?0:sv[h[t[u]]].back())+d[t[u]]);
    // d 按顺序存储了所有 dfs 序，s 是深度的前缀和
  }
  auto check=[&](int rt,int u){
    int lb=lower_bound(dv[h[u]].begin(),dv[h[u]].end(),l[rt])-dv[h[u]].begin(),
      ub=lower_bound(dv[h[u]].begin(),dv[h[u]].end(),l[rt]+e[rt])-dv[h[u]].begin()-1;
    return sv[h[u]][ub]-(lb?sv[h[u]][lb-1]:0)-1ll*(d[rt]-1)*(ub-lb+1)<=dv[h[u]].size();
  }; // 返回值为 false 表示 u 会使 rt 不合法
  vector<bool> ban(n),rs(n);
  for(int u=0;u<n;u++)
    for(int i=k,c=u;~i;i--){
      int v=f[c][i];
      if(v<0)continue;
      if(!ban[v]&&check(v,u))c=v;
      else while(~v&&!ban[v])ban[v]=true,v=f[v][0];
    } // 倍增过程，加了点小优化
  for(int u=0;u<n;u++)
    if(!ban[u]&&es[u]+m==n)rs[h[u]]=true;
  // 检查 M 的条件是否满足
  cout<<count(rs.begin(),rs.end(),true)<<endl;
  return 0;
}