ProblemE Equidistant (DFS)

題目大意：

有一張地圖，有幾個需要參加 ICPC 的城市，我們需要設計一個程式，尋找一個城市可以讓每個要參加 ICPC 的城市都是花相同的距離到達?

分析：

此題有很多種做法，但唯有時間複雜度最低才能 AC (我怎麼覺得我好像在說廢話 XD)

先透過 DFS 把參加 ICPC 中的城市兩個最遠距離給求出來。
再將兩個城市中的最長距離 /2 ，再找出那個路經的城市(定義為 A)。

再透過 DFS 從 A 開始到每一個需要參加 ICPC 的城市，如果他們的距離不等於我們在上個 DFS 找出的最長距離 /2，就輸出 “NO” ，如果都可以那就輸出 “YES”

P.S. 我好久沒有寫 DFS 了，居然都快忘記了。這邊就要感謝 BILL。
喚醒我那在史前時代的記憶用 vector 去做 DFS，真的優秀。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
int m , n , flag=1;
int Maxn_city = 0 , Maxn_path = 0 ;
vector<int>tree[200020] ;
int city[200020] = {} ;
int visit[200020] = {} ;
vector<int> travel ;

void BFS_to_large_path(int root ){
    visit[root] = 1 ;
    travel.push_back(root);
    for(int i = 0 ; i < tree[root].size() ; i++){
        int node = tree[root][i] ;
        if(!visit[node]){
            BFS_to_large_path(node);
            travel.pop_back();
            visit[root] = 0 ;
        }
    }
    //debug to check large path
    //if (root == 1)
    //    cout << "1=" << travel.size() << ' ' << Maxn_path << ' ' << city[root] << '\n' ;

    if(city[root] && travel.size() > Maxn_path){
        Maxn_city = travel[travel.size()/2];
        Maxn_path = travel.size();
    }
}

void BFS_to_other_path(int root ,int path){
    visit[root] = 1 ;
    for(int i = 0 ; i < tree[root].size() ; i++){
        int node = tree[root][i] ;
        if(!visit[node]){
            BFS_to_other_path(node , path+1);
            visit[root] = 0 ;
        }
    }
    //debug
    if(root == 1 )
        cout << "city=" << root << " path= " << path << '\n' ;

    if(city[root] && path != Maxn_path)
        flag = 0 ;
}


int main(){
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin);
#endif // LOCAL
    cin >> n >> m ;
    int a , b ;
    for(int i = 0 ; i < n-1 ; i++){
        cin >> a >> b ;
        tree[a].push_back(b) ;
        tree[b].push_back(a) ;
    }

    for(int i = 0 ; i < m ; i++){
        cin >> a ;
        city[a] = 1 ;
    }
    BFS_to_large_path(a);
    //visit[a] = 0 ;
    BFS_to_other_path(Maxn_city , 1 );
    if(flag)
        cout << "YES\n" << Maxn_city ;
    else
        cout << "NO" ;

    //debug
    cout << "Maxn_path= " << Maxn_path << " Maxn_city= " << Maxn_city << '\n' ;
}