【AtCoder Grand Contest 009 D】Uninity | Mrsrz's blog

点分治思想，贪心。

题目大意：

定义：

• 一个结点的树是 Uninity $0$ 的树。
• 将 $x$（$x\geq 0$）棵 Uninity $k$ 的树连到一个结点上，形成的新树是 Uninity $k+1$ 的树。

显然，一棵 Uninity $k$ 的树，同时也是 Uninity $k+1,k+2,k+3,\cdots$ 的

给定一棵树，求最小的 $k$ 使得这棵树是 Uninity $k$ 的。

题解：

这个过程类似点分治，所以一个上界为 $\log_2n$。但答案可能比这个小。

点分治的一个性质为：任意两个在点分树中深度相同的点，它们在原树上的路径经过的结点中，必定存在一个结点，它在点分树上的深度比那两个结点都小。其中一个结点就是分治中心。

考虑这道题，我们要给每个结点标号，并满足：

1. 叶子结点标号为 $0$。
2. 两个标号相等的结点的简单路径上，存在一个结点的标号比它们大。
3. 标号最大的结点的标号最小。

我们对每棵子树进行贪心，状压记录所有的这个子树内出现的，并且 这个标号的结点 到当前根的路径中，不存在标号大于 这个标号的结点 的 标号。对于一个标号 $x$，如果它在至少两个子树中有记录，那么你当前结点的标号必然大于 $x$。如果它在一个子树中有记录，那么当前结点的标号就不能为 $x$（否则两个 $x$ 中间就不存在比 $x$ 大的结点，不满足条件）。我们在能取的标号中取最小的即可。可以用一系列位运算来实现。

时间复杂度 $O(n)$。

Code：

#include<iostream>
#include<vector>
#include<algorithm>
typedef unsigned u32;
using namespace std;
const int N=1e5+5;
vector<int>G[N];
int n,g[N];
u32 f[N];
void dfs(int now,int pre){
    u32 x=0,y=0;
    for(int to:G[now])if(to!=pre){
        dfs(to,now);
        x|=y&f[to],y|=f[to];
    }
    if(y==0)f[now]=1;else{
        g[now]=__builtin_ctz(~y&(-(1u<<(32-(x?__builtin_clz(x):32)))));
        f[now]=y>>g[now]<<g[now]|(1<<g[now]);
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v),G[v].push_back(u);
    }
    dfs(1,0);
    cout<<*max_element(g+1,g+n+1)<<'\n';
    return 0;
}