AT2293 [AGC009D] Uninity（贪心、状压）

解析

题意描述令人一脸懵逼…
看了一下样例再回去看那个uninity的定义才大概明白，题目所求的其实就是按照给出树构造的点分树的最大深度的最小值。

然后…就不会辣qwq
一开始的方向就错了，尝试通过确定分治重心来考虑，还真发现了一些挺有意思的性质，然鹅并没有啥用…

一个关于点分树非常经典的等价转换：给每个点赋一个权值作为深度，那么赋值方案合法当且仅当 $\forall de{p}_i=de{p}_j=x,\exists k\in path(i,j),de{p}_k<x$。
为了方便，我们可以把深度取反，这样最后的符号就反过来了，比较好考虑。
然后从叶子往上贪心的确定每个节点的最小深度，定义集合： b a n x = { k ∣ d s o n = k , s o n ∈ s u b t r e e ( x ) , ∄ y ∈ p a t h ( s o n , x ) , d y > k } ban_{x}=\{k|d_{son}=k,son\in subtree(x),\not\exists y\in path(son,x),d_y>k\} banx​={ k∣dson​=k,son∈subtree(x),​∃y∈path(son,x),dy​>k} 。
首先，当前点x肯定不能填属于任意一个儿子ban集合的值；同时，如果存在两个儿子 $x,y$ 使得它们的ban集合都有k，那么x的取值就必须大于k。
由于答案是 $O(\log n)$ 的，模拟即可，总复杂度 $O(n\log n)$。
（使用 built_in 函数似乎可以做到线性）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
using namespace std;

const int N=1e5+100;
const double eps=1e-10;
const int mod=998244353;
inline ll read(){
    
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {
    if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)) {
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}

inline ll ksm(ll x,ll k){
    
  ll res(1);
  while(k){
    
    if(k&1) res=res*x%mod;
    x=x*x%mod;
    k>>=1;
  }
  return res;
}

int n,m,k;
int ban[N],f[N];
vector<int>e[N];
int ans;
void dfs(int x,int fa){
    
  int s(0),t(0);
  for(int to:e[x]){
    
    if(to==fa) continue;
    dfs(to,x);
    ban[x]|=ban[to];
    t|=(s&ban[to]);
    s|=ban[to];
  }
  for(int i=20;i>=0;i--){
    
    if(t&(1<<i)) break;
    if((s&(1<<i))==0) f[x]=i;
  }
  for(int i=0;i<f[x];i++){
    
    if(ban[x]&(1<<i)) ban[x]^=(1<<i);
  }
  ban[x]|=(1<<f[x]);
  ans=max(ans,f[x]);
}

signed main(){
    
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
  n=read();
  for(int i=1;i<n;i++){
    
    int x=read(),y=read();
    e[x].push_back(y);
    e[y].push_back(x);
  }
  dfs(1,0);
  printf("%d\n",ans);
  return 0;
}