[TIOJ 1575] 欸西國的欸西M大賽(Accepted)

作法：

這題其實和 HOJ 79 滅人器很像，只不過這題裡的滅人器可以供應無限多個節點。這樣我的作法就會爛掉的......後來看了這篇才領悟他的精髓(?)

作法就和這篇裡的第二個作法類似。首先當然是二分答案，所以問題變成，給定一個 d 值，是否能選出 <= k 個考場，使得每個點到離他最近的考場的距離都<=d 。

考慮一個子樹，它下面已經設好幾個考場了(或沒有)，那麼這顆子樹的最深的還沒被蓋到的節點是最重要的，而在所有沒被蓋到的結點裡也只需要考慮這個，因為當最深的點被蓋到了那其他當然也被蓋到了。而在這顆子樹中設的考場們，只需要考慮深度最淺的那個，因為他最有機會去覆蓋這個子樹的根節點的其他兄弟子樹裡的未蓋點。所以對每個子樹，設 dp[ x ] 代表：若以 x 為根的子樹裡還有未蓋點，那麼他的值就是未蓋點離 x 的距離的最大值。而如果沒有未蓋點，那他的值就是「 x 的子樹中設的考場離 x 的距離的最小值」 - d 。這樣在處理每個 x 的 dp 值的時候，先求出他子樹的 dp 值的最大和最小值，就可以分成以下幾種情況：

1. 最大值 >= d-1 ，代表 x 這個點一定要設個考場。
2.  x 的子樹中都沒有未蓋點，那麼 dp[ x ] 就是子樹的最小 dp 值 +1，但如果子樹的最小 dp 值是0那就是0 。
3. x 的子樹中，深度最淺的考場可以蓋掉所有的未蓋點，那麼 dp[ x ] 就是子樹的最小 dp 值 +1。
4. 如果殺不掉，那代表 x 的子樹還有未蓋點，所以 dp[ x ] 就是子樹最大的 dp 值 +1 。

最後根結點的情形要特別注意，如果 dp[ root ] > 0 ，則需要再多設一個考場。
另外這題的記憶體卡很緊......如果用 vector 存邊會MLE，所以我就把邊的存法改成和上面網址的 code 一樣，用 linked list 來存，竟然就不會MLE了......。另外寫遞回型DFS真的會RE，所以要乖乖寫 stack QQ 。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10 ;
 
struct edge{
    int j;
    edge *next;
}*v[maxn],e[maxn*2],*ptr,*nowe;
void Set(int i,int j){
    static int ccnt=0;
    nowe=&e[ccnt++];
    ptr=v[i];
    v[i]=nowe;
    nowe->j=j;
    nowe->next=ptr;
}
 
int st[maxn] ;
int k ;
int dp[maxn],fa[maxn] ;
 
bool check(int num)
{
    int sz=1 ; st[0]=1 ; fa[1]=1 ;
    int cnt=0 ;
    while(sz)
    {
        int u=st[sz-1] ; sz-- ;
        if(u>0)
        {
            st[sz++]=-u ;
            for(edge *ptr=v[u];ptr;ptr=ptr->next)
                if(ptr->j!=fa[u])
                st[sz++]=ptr->j , fa[ptr->j]=u ;
            continue ;
        }
        u=-u ;
        int sup=0 , dem=-1 ;
        for(edge *ptr=v[u];ptr;ptr=ptr->next)
            if(ptr->j!=fa[u])
            sup=min(sup,dp[ptr->j]) , dem=max(dem,dp[ptr->j]) ;
        if(dem>=num-1)
        {
            if(++cnt > k) return 0 ;
            dp[u]=-num ;
        }
        else if(dem<0) dp[u]= sup<0 ? sup+1 : 0 ;
        else if(-sup-2>=dem) dp[u]=sup+1 ;
        else dp[u]=dem+1 ;
    }
    if(dp[1]>0 && ++cnt>k) return 0 ;
    return 1 ;
}
 
main()
{
    int n,m ; scanf("%d%d%d",&n,&m,&k) ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        Set(x,y) ;
        Set(y,x) ;
    }
 
    if(k==n) { printf("0\n") ; return 0 ; }
    if(k==0) { printf("%d\n",n-1) ; return 0 ; }
    int l=0 , r=n ;
    while(r-l>1)
    {
        int mid=(r+l)/2 ;
        if(check(mid)) r=mid ;
        else l=mid ;
    }
    printf("%d\n",r) ;
}