[EGOI2024] Team Coding 题解

FFTotoro · 2025-01-19 20:05:44 · 题解

数据范围提示我们进行根号分治。

选定一个阈值 B。对于使用人数 \le B 的编程语言（不妨认为出现了 c 次），枚举团队领导 u，再暴力枚举其他使用该编程语言的人对应的结点，如果该结点本来不在 u 子树内并且 u 子树内对应深度有“空位”（即可以与其交换，并使答案增大的结点），那么对其进行一次操作，使其进入 u 的子树内。处理子树内空位数量可以对于每个深度预处理出所有的点的 dfs 序，子树查就变成了区间查，直接 lower_bound 就可以了。这一部分的时间复杂度为 O(c^2\log c)。

对于使用人数 >B 的编程语言，仍然考虑每个团队领导 u，对于每个深度考虑，第一个答案（人数）即为“u 的子树内该深度的结点个数”与“整棵树中使用该编程语言且位于该深度的人数”的较小值，将它们求和即为总答案；第二个答案（操作次数）只需在第一个答案的基础上直接减去“u 子树内使用该编程语言且位于该深度的人数”。以上需要的所有信息可以直接在整棵树上借助 std::unordered_map 做启发式合并。这一部分的时间复杂度为 O(n\log n)。

取 B=\sqrt{n}，总的时间复杂度为 O(n\sqrt{n}\log n)。实际实现中可以根据两个做法的运行效率进行平衡，例如代码中取了 B=\min\{n,6\sqrt{n}\}。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
inline void upd(pii &x,pii y){
  if(y.first>x.first||y.first==x.first&&y.second<x.second)x=y;
} // 更新答案
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,k,b,o=0; cin>>n>>k,b=min(n,(int)sqrt(n)*6);
  vector<int> l(n),d(n),e(n,1),od(n),dr(n,-1);
  vector<vector<int> > ls(k),pd(n);
  for(int i=0;i<n;i++)
    cin>>l[i],ls[l[i]].emplace_back(i);
  vector<vector<int> > g(n);
  for(int i=1;i<n;i++){
    int f; cin>>f;
    g[f].emplace_back(i);
  }
  function<void(int)> dfs=[&](int u){
    pd[d[u]].emplace_back(od[u]=o++);
    for(int i:g[u])
      d[i]=d[u]+1,dfs(i),e[u]+=e[i];
  };
  dfs(0); // 预处理一些信息
  auto isanc=[&](int u,int v){
    return od[u]<=od[v]&&od[v]<od[u]+e[u];
  }; // 判断 u 是否是 v 的祖先
  pii rs(1,0);
  for(int i=0;i<k;i++){
    if(ls[i].size()<=b){
      for(int u:ls[i]){
        int nb=1,tm=0;
        for(int v:ls[i]){
          if(d[v]<=d[u])continue;
          if(dr[d[v]]<0){
            dr[d[v]]=lower_bound(pd[d[v]].begin(),pd[d[v]].end(),od[u]+e[u])
              -lower_bound(pd[d[v]].begin(),pd[d[v]].end(),od[u]);
          }
          if(isanc(u,v))dr[d[v]]--,nb++;
        } // 处理空位数
        for(int v:ls[i])
          if(!isanc(u,v)&&dr[d[v]]>0)dr[d[v]]--,nb++,tm++;
          // 往空位里头塞
        upd(rs,make_pair(nb,tm));
        for(int v:ls[i])
          dr[d[v]]=-1;
      }
    }
    else{
      vector<unordered_map<int,int> > em(n);
      vector<int> cd(n),c(n),r(n);
      for(int u:ls[i])cd[d[u]]++;
      auto add=[&](int u,int d,int x){
        int &w=em[u][d];
        r[u]-=min(cd[d],w);
        r[u]+=min(cd[d],w+=x);
      }; // 合并答案
      function<void(int)> dfs2=[&](int u){
        int h=-1,mx=0;
        for(int i:g[u]){
          dfs2(i),c[u]+=c[i];
          if(em[i].size()>mx)mx=em[i].size(),h=i;
        }
        if(~h)em[u].swap(em[h]),r[u]=r[h];
        for(int i:g[u])
          if(i!=h){
            for(auto [x,y]:em[i])
              add(u,x,y);
          }
        add(u,d[u],1);
        if(l[u]==i)c[u]++,upd(rs,make_pair(r[u],r[u]-c[u]));
      };
      dfs2(0);
    }
  }
  cout<<rs.first<<' '<<rs.second<<endl;
  return 0;
}