CCCPaste

Untitled

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 50005;
vector > graph[maxn];
int imp[maxn];
int cnt[maxn];
int n;
void bfs(int S) {
    queue q;
    q.push(S);
    q.push(0);
    vector parent(maxn, -1);
    vector visited(n, false);
    visited[S] = true;
    int max_dist = 0, F = 0;
    while(!q.empty()) {
        int c = q.front();
        q.pop();
        int dist = q.front();
        q.pop();
        if(imp[c]) {
            if(max_dist < dist) {
                max_dist = dist;
                F = c;
            }
        }
        for(int i = 0; i < (int) graph[c].size(); i++) {
            int neighbour = graph[c][i].first;
            int weight = graph[c][i].second;
            if(!visited[neighbour]) {
                visited[neighbour] = true;
                q.push(neighbour);
                q.push(dist + weight);
                parent[neighbour] = c;
            }
        }
    }
//    cout << max_dist <<" " << F <<  endl;
    
    int A = S, B = F;
    while(B != A){
        cnt[B]++;
        B = parent[B];
    }
    cnt[A]++;
    
}
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    
    for(int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }
    int k;
    cin >> k;
    memset(imp, false, sizeof imp);
    for(int i = 0; i < k; i++) {
        int x;
        cin >> x;
        imp[x] = true;
    }
    for(int i = 0; i < n; i++) {
        if(imp[i]) {
            bfs(i);
        }
    }
    int res = 0, saved = 0;
    for(int i = 0; i < n; i++) {
        if(cnt[i] > res) {
            res = cnt[i];
            
        }
    }
    for(int i = 0; i < n; i++) {
        
        if(cnt[i] == res) {
            saved++;
//            cout << i << endl;
        }
    }
    
    cout << res << " " << saved << endl;
    
    return 0;
                
}
// NNNNNNNNaN