TIOJ 1575 欸西國的欸西M大賽(Accepted) [97校內 prob6]

 poao899    36288K    16822MS    G++     1.68K     2010-03-08 17:25:08                                                   .



題意是這樣的，給你一棵樹，n<10^6，選出k個點(k<10^6)，

請問對於每個樹上的點，要走到這k個點的最短距離的最大值是多少？













Hint:





對答案二分搜，

再從樹葉Greedy

噢對了記得要寫stack



//****************************************

#include<stdio.h>
#define MAXN 2000100
struct edge{
    int j;
    edge *next;
}*v[MAXN],e[MAXN*2],*ptr,*nowe;
void set(int i,int j){
    static int cnt=0;
    nowe=&e[cnt++];
    ptr=v[i];
    v[i]=nowe;
    nowe->j=j;
    nowe->next=ptr;
}
int ar[MAXN],top;
int dp[MAXN],dmax,dnow;
int max[MAXN],min[MAXN],fa[MAXN];
int n,m,k,a,b;
bool can,visited[MAXN];
bool chk(){
    can=1;dnow=0;
    for(int i=0;i<=n;i++)
        visited[i]=0;
    ar[1]=top=1;
    while(top){
        int now=ar[top];
        if(!can)return 0;
        if(now>0){
            max[now]=-1;min[now]=0;
            visited[now]=1;
            dp[now]=0;
            ar[top]=-now;
            int max=-1,min=0;
            for(edge *ptr=v[now];ptr;ptr=ptr->next){
                if(visited[ptr->j]){
                    fa[now]=ptr->j;
                    continue;
                }
                ar[++top]=ptr->j;
            }
        }else{
            now=-now;
            if(max[now]>=dmax-1){
                dp[now]=-dmax;
                dnow++;
                if(dnow>k)
                    can=0;
            }
            else if(max[now]<0){
                if(min[now]<0)
                    dp[now]=min[now]+1;
            }
            else{
                if(-min[now]-2>=max[now])
                    dp[now]=min[now]+1;
                else
                    dp[now]=max[now]+1;
            }
            if(dp[now]>max[fa[now]])
                max[fa[now]]=dp[now];
            if(dp[now]<min[fa[now]])
                min[fa[now]]=dp[now];
            top--;
        }
    }
    if(dp[1]>0)dnow++;
    return can&&dnow<=k;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    if(n==k){puts("0");return 0;}
    else if(k==0){printf("%d\n",n-1);return 0;}
    if(n-1!=m)for(;;)puts("XDD");
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        set(a,b);
        set(b,a);
    }
    int _l=0,_r=n;
    while(_l!=_r){
        dmax=(_l+_r)/2;
        if(!chk())
            _l=dmax+1;
        else _r=dmax;
    }
    printf("%d\n",_l);
}