申请注册商标需要多少钱,东莞网络优化公司排名,vue做网站的优缺点,做网站简单正题
题目链接:https://www.luogu.com.cn/problem/AT2293 题目大意
给出一棵树#xff0c;求它一棵点分树的最小深度。 1≤n≤1051\leq n\leq 10^51≤n≤105 解题思路
点分树的做法是直接找重心#xff0c;但是两个重心我们很难确定找哪个#xff0c;所以这个方法行不通。…正题
题目链接:https://www.luogu.com.cn/problem/AT2293 题目大意
给出一棵树求它一棵点分树的最小深度。
1≤n≤1051\leq n\leq 10^51≤n≤105 解题思路
点分树的做法是直接找重心但是两个重心我们很难确定找哪个所以这个方法行不通。
但是这样我们大概能确定答案的上界是logn\log nlogn级别的。考虑我们记每个点的点分子树深度did_idi那么did_idi肯定满足对于一对深度相同的(x,y)(x,y)(x,y)它们的路径上肯定存在一个点zzz满足dzdx,dzdyd_zd_x,d_zd_ydzdx,dzdy。
那么同样的如果我们得到一个满足这个条件的数组ddd我们也能构造出一棵合法的点分树所以我们的目的就是要最小化ddd的值。
考虑一个构造方法对于一个节点xxx的深度ppp首先如果它的儿子中有深度为ppp的点那么显然不合法如果存在一个在它不同子树中的节点yyy的深度≥p\geq p≥p并且x↔yx\leftrightarrow yx↔y路径上节点深度都不超过ppp那么显然也不合法。
显然上面这两个条件我们可以用状压搞定。
但是这样构造为什么是合法的呢我也不知道只能感性证明一下。能发现我们的操作中如果一个节点xxx选择了深度ppp那么它往上的限制中所有深度ppp的限制都会被打开也就是说实际上选择更大的深度并不会放松后面的限制所以选最小的更优。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
struct node{int to,next;
}a[N1];
int n,tot,ls[N],f[N],ans;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x,int fa){int p0,s0;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dfs(y,x);for(int j30;j0;j--)if(sf[y](1j)){pmax(p,j1);break;}s|f[y];}while((sp)1)p;ansmax(ans,p);f[x]s|((1p1)-1);f[x]f[x]^((1p)-1);return;
}
int main()
{scanf(%d,n);for(int i1,x,y;in;i){scanf(%d%d,x,y);addl(x,y);addl(y,x);}dfs(1,0);printf(%d\n,ans);return 0;
}
