传送门:

AtCoder

洛谷


题目大意:

定义一个单独的节点为一棵\rm Uninity~0的树。

x(x \geqslant 0)\rm Uninity~k的树全部连到一个节点上形成的树,称之为一棵\rm Uninity~k+1的树。

显然,一棵\rm Uninity~k的树,同样也是一棵\rm Uninity~k+1,k+2,k+3 \cdots的树。

现在给你一棵树,求一个最小的k使得这棵树是一棵\rm Uninity~k的树。

解题思路:

若我们把定义中提到的点v赋一个点权k+1,权值为0的树的点点权赋为0,问题可以等价地转化为给树上每个点定点权,使得任意两个点权相等的点为端点的树上简单路径上至少存在一个点权大于这两点点权的点,最小化最大的点权。

假设bit_i为以i为根的子树的权值,我们认为一个权值k对于一个点x是待处理的当且仅当:x的权值为k或者x子树内某一点权值为k并且到x的路径上没有一个点>k

我们可以发现,对于点x

  • 如果x有两棵子树有权值k待处理,那么x的权值就>k
  • 如果x只有一个子树有权值k待处理,那么x的权值就不能=k

根据点分治的思想最大的权值不会超过logn,所以可以二进制压位解决。

Code:

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
struct edge{int to,nxt;}e[maxn<<1];
int tot,ans,head[maxn],bit[maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
void add(int u,int v){e[++tot].to=v;e[tot].nxt=head[u];head[u]=tot;}
void dfs(int x,int fa){
    int limit=0;
    for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to){
        if(v==fa)continue;dfs(v,x);
        limit|=bit[x]&bit[v];
        bit[x]|=bit[v];
    }int mx=20;
    while(mx>=0&&(!(limit&(1<<mx))))mx--;mx++;
    while(bit[x]&(1<<mx))mx++;bit[x]|=1<<mx;
    ans=max(ans,mx);bit[x]=bit[x]>>mx<<mx;
}
int main(){
    int n=read();
    for(int i=1;i<n;i++){int u=read(),v=read();add(u,v);add(v,u);}
    dfs(1,0);write(ans);
    return 0;
}

发表评论