题面
贝茜被农民们逼进了一个偏僻的农场. 农场可视为一棵有 N 个结点的树, 结点分别编号为 1,2,...,N . 每个叶子结点都是出入口. 开始时, 每个出入口都可以放一个农民 (也可以不放). 每个时刻, 贝茜和农民都可以移动到相邻的一个结点. 如果某一时刻农民与贝茜相遇了 (在边上或点上均算), 则贝茜将被抓住. 抓捕过程中, 农民们与贝茜均知道对方在哪个结点.
请问: 对于结点 i\((1\leq i\leq N)\), 如果开始时贝茜在该结点, 最少有多少农民, 她才会被抓住.
分析
先考虑问题的简化版, 对于给定的起点 s 求出答案
设 dist(x,y) 表示 x,y 两点之间的距离
我们发现, 对于某一个节点 x, 若 $dist(s,x) \geq \min {dist(x,u) } $ 其中 u 为 x 的子树中的叶子节点, 那么从 x 走到 s 的时
候就会被抓住.$\min {dist(x,u) } $ 可以通过一次 BFS 预处理出来
显然奶牛越早被抓住更好, 从节点 s 出发 DFS, 只要当前节点 x 满足上述条件, 则 ans++, 并不访问 x 子树中的节点. 因为如果在 x 点被抓住了, 它就不会到比 x 深度更大的节点去了
这样的复杂度显然是 \(O(n^2)\)
有一个玄学优化, 可以通过此题, 方法如下
1.DP 一遍求出每个点到最近的叶子节点的距离 dp[x]
2.DFS, 把链缩成一条边, 因为可以发现不管在链的哪里拦截都是一样的
3. 每次暴力, 当 dp[x]<=dist(x,root) 的时候 ans++,return
可以证明把链缩掉之后是 \(O(n\sqrt{n})\) 的
由于没有链, 我们可以把模型简化为一个满 k 叉树 (k>1), 每次暴力 DFS, 显然 DFS 的深度不超过树的深度的 1/2, 即 \(O(log_kn)\)
访问的子树大小为
\[1+k+k^2+...+k^{\frac{1}{2}\log_kn}=\frac{k^{(\frac{1}{2}\log_kn)+1}-1}{k-1}=\frac{k^{\log_kn} \times \sqrt k-1}{k-1}=\frac{k\sqrt{n}-1}{k-1}=\sqrt{n}+\frac{\sqrt{n}-1}{k-1}\]
显然当 k=2 最大, 为 \(2\sqrt{n}-1\),
所以总时间复杂度为 \(O(n\sqrt{n})\), 与分块相同, 且常数远小于点分治
代码
- #include<iostream>
- #include<cstdio>
- #include<queue>
- #include<cstring>
- #define maxn 100005
- #define INF 0x3f3f3f3f
- using namespace std;
- inline void qread(int &x){
- x=0;
- char c=getchar();
- while(c<'0'||c>'9'){
- c=getchar();
- }
- while(c>='0'&&c<='9'){
- x=x*10+c-'0';
- c=getchar();
- }
- }
- inline void qprint(int x){
- if(x==0){
- putchar('0');
- return;
- }else{
- if(x>=10) qprint(x/10);
- putchar(x%10+'0');
- }
- }
- int n,k;
- struct edge{
- int from;
- int to;
- int next;
- int nfrom;
- int nto;
- int len;
- }E[maxn<<1];
- int head[maxn];
- int deg[maxn];
- int sz=1;
- void add_edge(int u,int v){
- deg[u]++;
- deg[v]++;
- sz++;
- E[sz].from=u;
- E[sz].to=v;
- E[sz].next=head[u];
- head[u]=sz;
- }
- int dp[maxn];// 表示离 x 最近的叶子节点到 x 的距离
- // 不能从一个根开始 DFS, 因为此时根不定,
- // 到一个点最近的叶子节点不一定在 DFS 时的子树里, 而可能在它上方
- void bfs(){
- queue<int>q;
- for(int i=1;i<=n;i++){
- if(deg[i]<=1){
- q.push(i);
- dp[i]=0;
- }else dp[i]=INF;
- }
- while(!q.empty()){
- int x=q.front();
- q.pop();
- for(int i=head[x];i;i=E[i].next){
- int y=E[i].to;
- if(dp[y]==INF){
- dp[y]=min(dp[y],dp[x]+1);
- q.push(y);
- }
- }
- }
- }
- int s,t,d;
- void dfs2(int x,int fa,int deep){
- if(fa!=0&°[x]!=2){
- s=x;
- t=fa;
- d=deep;
- return;
- }
- for(int i=head[x];i;i=E[i].next){
- int y=E[i].to;
- if(y!=fa){
- dfs2(y,x,deep+1);
- E[i].nto=s;
- E[i].nfrom=t;
- E[i].len=d-deep;
- }
- }
- }
- int ans=0;
- void dfs3(int x,int fa,int deep){
- if(deep>=dp[x]){
- ans++;
- return;
- }
- for(int i=head[x];i;i=E[i].next){
- int y=E[i].to;
- if(y!=fa){
- dfs3(E[i].nto,E[i].nfrom,deep+E[i].len);
- }
- }
- }
- int main(){
- int u,v;
- qread(n);
- for(int i=1;i<n;i++){
- qread(u);
- qread(v);
- add_edge(u,v);
- add_edge(v,u);
- }
- for(int i=1;i<=n;i++) deg[i]/=2;
- bfs();
- for(int i=1;i<=n;i++){
- if(deg[i]!=2) dfs2(i,0,0);
- }
- for(int i=1;i<=n;i++){
- ans=0;
- dfs3(i,0,0);
- qprint(ans);
- putchar('\n');
- }
- }
来源: http://www.bubuko.com/infodetail-2994189.html