Submission #64792856

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
vector<int> bfs(int start, const vector<vector<int>> &g) {
    int n = g.size();
    vector<int> dist(n, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for (int nx : g[cur]){
            if(dist[nx] == -1){
                dist[nx] = dist[cur] + 1;
                q.push(nx);
            }
        }
    }
    return dist;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
vector<int> bfs(int start, const vector<vector<int>> &g) {
    int n = g.size();
    vector<int> dist(n, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for (int nx : g[cur]){
            if(dist[nx] == -1){
                dist[nx] = dist[cur] + 1;
                q.push(nx);
            }
        }
    }
    return dist;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N1;
    cin >> N1;
    vector<vector<int>> tree1(N1+1);
    for (int i = 1; i <= N1-1; i++){
        int u, v;
        cin >> u >> v;
        tree1[u].push_back(v);
        tree1[v].push_back(u);
    }
    int N2;
    cin >> N2;
    vector<vector<int>> tree2(N2+1);
    for (int i = 1; i <= N2-1; i++){
        int u, v; cin >> u >> v;
        tree2[u].push_back(v);
        tree2[v].push_back(u);
    }
 
    auto d1 = bfs(1, tree1);
    int A = 1;
    for (int i = 1; i <= N1; i++){
        if(d1[i] > d1[A]) A = i;
    }
    auto dA = bfs(A, tree1);
    int B = A;
    for (int i = 1; i <= N1; i++){
        if(dA[i] > dA[B]) B = i;
    }
    auto dB = bfs(B, tree1);
    vector<int> F1(N1+1);
    int D1 = 0;
    for (int i = 1; i <= N1; i++){
        F1[i] = max(dA[i], dB[i]);
        D1 = max(D1, F1[i]);
    }

    auto d2 = bfs(1, tree2);
    int C_end = 1;
    for (int j = 1; j <= N2; j++){
        if(d2[j] > d2[C_end]) C_end = j;
    }
    auto dC = bfs(C_end, tree2);
    int D_end = C_end;
    for (int j = 1; j <= N2; j++){
        if(dC[j] > dC[D_end]) D_end = j;
    }
    auto dD = bfs(D_end, tree2);
    vector<int> F2(N2+1);
    int D2 = 0;
    for (int j = 1; j <= N2; j++){
        F2[j] = max(dC[j], dD[j]);
        D2 = max(D2, F2[j]);
    }
 
    int C_val = max(D1, D2);
 
    vector<int> arrF2;
    arrF2.reserve(N2);
    for (int j = 1; j <= N2; j++){
        arrF2.push_back(F2[j]);
    }
    sort(arrF2.begin(), arrF2.end());
    vector<ll> prefix(N2+1, 0);
    for (int j = 0; j < N2; j++){
        prefix[j+1] = prefix[j] + arrF2[j];
    }
 
    ll res = 0;
    for (int i = 1; i <= N1; i++){
        int x = F1[i];
        int threshold = C_val - 1 - x;
        int pos = lower_bound(arrF2.begin(), arrF2.end(), threshold + 1) - arrF2.begin();
        ll cnt_low = pos;
        ll cnt_high = N2 - pos;
        ll sum_high = prefix[N2] - prefix[pos];
        ll contrib = cnt_low * (ll)C_val + cnt_high * (ll)(x + 1) + sum_high;
        res += contrib;
    }
    cout << res << "\n";
    return 0;
}

Submission Info

Judge Result