Description

小 M 的宠物猫 CC 昨天干了背叛主人的事,于是她逃到一个远方的迷
宫躲藏了起来。
这个迷宫包含 N(用 1..N 编号) 个路口和 N-1 条连接两个路口的双向
隧道。 所以每两个路口之间都有唯一的路径。每个只与一条隧道相连的路
口都是迷宫的出口。
小 M 非常生气, 决定派出一些小狗从不同的出口出发尝试抓住 CC。 小
狗和 CC 的移动速度相同(在每个单位时间内,每个小狗都可以从一个路口
移动到相邻的一个路口,同时 CC 也可以这么做,当然他们在任意单位时间
都可以不移动,停留在原来的路口上)。 小狗们和 CC 总是知道对方在哪里。
如果在任意时刻,某个小狗和 CC 处于同一个路口或在穿过同一个隧道, 小
狗就可以抓住 CC。反过来,如果 CC 在小狗们抓住她之前到达一个出口, 于
是 CC 就逃脱了。
CC 不确定她能否成功逃脱,这取决于小狗的数量。给定 CC 当前所在的
路口 S,帮助小 M 确定为了抓住 CC 所需要的小狗的最小数量。假定小狗们
会自己选择最佳的方案来安排他们出发的出口。

Input

输入的第一行包含 N 和 S,分别表示路口数目和 CC 当前所在路口的编
号。接下来的 N–1 行,每行有两个整数(在 1~N 范围内)描述连接两个路
口的一条隧道。

Output

输出为了确保抓住 CC 所需的小狗的最小数量

Sample Input

7 1
1 2
1 3
3 4
3 5
4 6
5 7

Sample Output

3

Hint

对于 20%的数据: N≤3 00
对于 50%的数据: N≤5 000
对于 100%的数据: N≤100 000

Solution

首先对于起点即为出口的特判,当且仅当起点只有一个儿子,这时只需一只狗即可。
然后发现最坏情况是每个叶子节点都要一只狗,但狗可以跑过去拦截,所以将顶点与叶子节点路程割半,然后可以颜色染上下半段部分(使用树上倍增精准定位)当发现遍历到染过的时可以减1(用这次染色代替那次)如此下来便最优。
而由于是触碰返回,所以复杂度实际上是O(n)的。

上代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cctype>
#include<vector>
#include<queue>
#include<set>
#define maxn 100005 
using namespace std;
struct eage{
    int to,next;
}e[maxn<<1];
int np=0,first[maxn];
void add(int u,int v){
    e[++np]=(eage){v,first[u]};
    first[u]=np; 
}
int n,s,x,y,dep[maxn],fa[maxn][18];
int st[maxn],top=0;
bool ok=false;
void dfs(int i,int f,int d){
     dep[i]=d;fa[i][0]=f;
     for(int j=1;j<=17;j++) fa[i][j]=fa[fa[i][j-1]][j-1];
     int chd=0;
     for(int p=first[i];p;p=e[p].next){
         int j=e[p].to;
         if(j==f) continue;
         chd++;
         dfs(j,i,d+1);
     }    
     if(i==s&&chd==1) ok=true;
     if(chd==0) st[++top]=i;
}
/*int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    int x=dep[u]-dep[v];
    for(int i=0;i<=17;i++){
        if((1<<i)&x) u=fa[u][i];
    }
    if(u==v) return u;
    for(int i=17;i>=0;i--){
        if(fa[u][i]!=fa[v][i]) 
        u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0];
}*/
bool color[maxn];
int ans=0;
void dfss(int i){
    if(color[i]){ans--;return;}
    color[i]=1;
    for(int p=first[i];p;p=e[p].next){
        int j=e[p].to;
        if(j==fa[i][0])continue;
        dfss(j);
    }
}
void init(){
    scanf("%d%d",&n,&s);
    for(int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(s,0,0);
    if(ok==true) printf("1");
    else{
        for(int i=1;i<=top;i++){
            int x=dep[st[i]]-dep[s];
            x=x/2;
            int u=st[i];
            for(int j=0;j<=17;j++){
                if(x&(1<<j)) u=fa[u][j];
            }
            ans++;
            dfss(u);
        }
        printf("%d",ans);
    }
}
int main(){//实际复杂度只要O(n) 因为触碰返回 
    //freopen("escaping.in","r",stdin);
    //freopen("escaping.out","w",stdout);
    init();
    
    return 0;
}
Last modification:February 15th, 2019 at 09:51 pm