[HOJ 180][PA 2006]蟲蟲集結

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

先備知識: 樹的直徑
首先把這棵樹上色，使的任一條邊兩邊顏色不同，那麼每隔一小時，每隻蟲所在的節點顏色都會改變
因此，一開始先判斷是不是每隻蟲的節點顏色都一樣，如果不是的話輸出NIE
再來，可以發現如果有某個葉節點沒有蟲，那麼開會的地點選在這裡總沒有比選在旁邊的那個節點還要好(距離會多1)
所以可以先用queue把所有沒有蟲的葉節點刪除，不會影響答案
接著我們試著選一點u當作開會點，可以發現，離開會點最選的那隻蟲一定位於葉節點，因此，我們只考慮位於葉節點的蟲們
這樣問題就變成找離最遠的兩隻蟲(都要在葉節點)距離是多少了
答案就是樹的直徑/2
直徑一定會被2整除，請放心~~~(為甚麼呢？想想看吧XD)

code:

#include<cstdio>
#include<vector>
#include<cassert>
#include<queue>
#include<set>
using namespace std;
void getmax(int &a,const int b){if(b>a)a=b;}
set<int>ET[50000];
int Dfs(const int u,const int fa,int &mx)
{
    int h1=0,h2=0;
    for(const int nxt:ET[u])if(nxt!=fa)
    {
        const int th=Dfs(nxt,u,mx);
        if(th>=h1)h2=h1,h1=th;
        else if(th>h2)h2=th;
    }
    getmax(mx,h1+h2);
    return h1+1;
}
int N,M,K;
bool BUG[50000];
bool Check(const int u,const int fa,int color)
{
    if(BUG[u]&&color==1)return false;
    for(const int nxt:ET[u])if(nxt!=fa&&!Check(nxt,u,color^1))return false;
    return true;
}
void TrimLeaf()
{
    queue<int>q;
    for(int i=0;i<N;i++)if((int)ET[i].size()==1)q.push(i);
    while(!q.empty())
    {
        const int u=q.front();q.pop();
        if(BUG[u])continue;
        const int nxt=*ET[u].begin();
        ET[u].erase(nxt),ET[nxt].erase(u);
        if((int)ET[nxt].size()==1)q.push(nxt);
    }
}
int Solve()
{
    scanf("%d",&K);
    if(!K)return 0;
    int root=-1;
    for(int i=0;i<K;i++)scanf("%d",&root),BUG[--root]=true;
    TrimLeaf();
    if(!Check(root,-1,0))return -1;
    int ans=-1;
    Dfs(root,-1,ans);
    assert(ans%2==0);
    return ans/2;
}
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d%d",&N,&M),assert(N-1==M);
    for(int i=0;i<N;i++)ET[i].clear(),BUG[i]=false;
    for(int i=0,a,b;i<M;i++)
    {
        scanf("%d%d",&a,&b),a--,b--;
        ET[a].insert(b),ET[b].insert(a);
    }
    const int ans=Solve();
    if(ans==-1)puts("NIE");
    else printf("%d\n",ans);
    return 0;
}