bzoj2071：[POI2004]山洞迷宫

本文主要是介绍bzoj2071：[POI2004]山洞迷宫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：http://www.lydsy.com:808/JudgeOnline/problem.php?id=2071

题目大意：在Byteotia有一个洞穴. 它包含n 个洞室和一些隧道连接他们. 每个洞室之间只有一条唯一的路径连接他们. Hansel 在其中一个洞室藏了宝藏, 但是它不会说出它在哪. Gretel 想知道. 当她询问一个洞室是否有宝藏时,如果她猜对了Hansel 会告诉她,如果猜错了他会告诉她哪个方向会有宝藏.

给出洞穴的信息,那么无论Hansel 把宝藏藏在了哪,求出最少要询问多少次才能找到宝藏.

思路：首先考虑一种贪心，每次选重心。

但是这显然是错的。。。

不过这给我们一个提示，询问次数不会超过log2（n）

然后通过转换，这题就成了树顶点标号，

证明既不显然又不简单

对树顶点编号一题的解决可以参见：

http://wenku.baidu.com/link?url=AfOs9lDjrUbLV5xUviK0T-FwkVScFe8kMI6MmlwtGrxEB6qF4pzwhAzfRw-S_35eVxCKGoiu3bTQc5_Boi7tI7dpJ-lIHQby8AgLBdwRuve

S[x]表示x的子树中哪些标号到x点的路径上没有比它大的标号，实际是一个集合，程序中是一个二进制数
C[x]表示x的编号
F[x]表示在以i为根的子树中最少需要0到F[x]的整数标号

然后对于叶子节点

显然f[i]=0,S[i]={0}

对于非叶子结点

如果有两个子树的S中都有同一个标号c，那么C[x]至少是c+1，因为两个c的路径之间必须有一个比c大的标号，否则不合法。

而且C[x]不能再在任何一个子树的S集合中，也是这个原因，x到该点路径上已经没有未标号的点了。

于是

同时对于所有标号小于C[x]的结点将不会属于S[x]

考虑S[x]怎么求：

那么F[x]就很显然了，就是S[x]中的最大标号

#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn=50010,maxm=maxn<<1,init=(1<<18)-1,maxk=17;
using namespace std;
int pre[maxm],now[maxn],son[maxm],tot,n,f[maxn],S[maxn],c[maxn],ans=1e9,pw[maxk+3],cnt[maxk+3];
void add(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}
//S[x]表示x的子树中哪些标号到x点的路径上没有比它大的标号
//C[x]表示x的编号
//F[x]表示在以i为根的子树中最少需要0到F[x]的整数标号 void dfs(int x,int fa){int pp=0;for (int y=now[x];y;y=pre[y]) if (son[y]!=fa) dfs(son[y],x),pp++;//,printf("%d %d %d\n",x,son[y],S[son[y]])if (!pp){f[x]=0,S[x]=pw[0];return;}int res2=0,c0=0;S[x]=0;memset(cnt,0,sizeof(cnt));for (int y=now[x];y;y=pre[y]) if (son[y]!=fa){int v=son[y];res2|=S[v],S[x]|=S[v];for (int i=0;i<maxk;i++)if (S[v]&pw[i]) cnt[i]++;}for (c0=maxk;;c0--) if (cnt[c0]>=2||c0<=0) break;if (!c0&&!(S[x]&pw[0])) c0=-1;for (int i=c0+1;i<=maxk;i++) if (!(res2&pw[i])){c[x]=i;break;}for (int i=0;i<c[x];i++) S[x]-=(pw[i]&S[x]);S[x]|=pw[c[x]];for (int i=maxk;i;i--) if (S[x]&pw[i]){f[x]=i;break;}
}int main(){pw[0]=1;for (int i=1;i<=maxk+1;i++) pw[i]=pw[i-1]<<1;scanf("%d",&n);memset(f,63,sizeof(f));for (int i=1,a,b;i<n;i++) scanf("%d%d",&a,&b),add(a,b),add(b,a);dfs(1,0);printf("%d\n",f[1]);return 0;
}
/*
8
1 2
1 3
3 4
3 5
3 6
4 7
7 8