Submission #64783339

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef _Alignof
#define _Alignof __alignof__
#endif
#include <bits/stdc++.h>
#include <numeric>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
#define yes "Yes"
#define no "No"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
const vector<char> alpha = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#ifndef _Alignof
#define _Alignof __alignof__
#endif
#include <bits/stdc++.h>
#include <numeric>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
#define yes "Yes"
#define no "No"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
const vector<char> alpha = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
const ll INF = 1e18;


vector<int> bfs(int s,int n,vector<vector<int>>&g){
    vector<int> dist(n,-1);
    dist[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(auto &w:g[u]){
            if(dist[w]<0){
                dist[w]=dist[u]+1;
                q.push(w);
            }
        }
    }
    return dist;
}

tuple<vector<int>,vector<int>,int> find_diameter(int n,vector<vector<int>>&g){
    auto d0=bfs(0,n,g);
    int x=0; 
    for(int i=0;i<n;i++){
        if(d0[i]>d0[x])x=i;
    }
    auto dx=bfs(x,n,g);
    int y=0;
    for(int i=0;i<n;i++){
        if(dx[i]>dx[y])y=i;
    }
    auto dy=bfs(y,n,g);
    return {dx,dy,dx[y]};
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N1;cin>>N1;
    vector<vector<int>> g1(N1);
    for(int i=0;i<N1-1;i++){
        int a,b;cin>>a>>b;--a;--b;
        g1[a].push_back(b);
        g1[b].push_back(a);
    }
    auto [dx1,dy1,D1]=find_diameter(N1,g1);
    vector<int> e1(N1);
    for(int i=0;i<N1;i++){
        e1[i]=max(dx1[i],dy1[i]);
    }
    int N2;cin>>N2;
    vector<vector<int>> g2(N2);
    for(int i=0;i<N2-1;i++){
        int a,b;cin>>a>>b;--a;--b;
        g2[a].push_back(b);
        g2[b].push_back(a);
    }
    auto [dx2,dy2,D2]=find_diameter(N2,g2);
    vector<int> e2(N2);
    for(int i=0;i<N2;i++){
        e2[i]=max(dx2[i],dy2[i]);
    }
    sort(e1.begin(),e1.end());
    sort(e2.begin(),e2.end());
    long long M=max((long long)D1,(long long)D2),ans=M*( (long long)N1*N2 );
    vector<long long> p2(N2+1,0);
    for(int i=0;i<N2;i++){
        p2[i+1]=p2[i]+e2[i];
    }
    for(auto &A:e1){
        long long t=M-A-1;
        auto idx=lower_bound(e2.begin(),e2.end(),t+1)-e2.begin();
        if(idx<(long long)N2){
            long long cnt=N2-idx;
            long long s=p2[N2]-p2[idx];
            ans+=( (long long)(A+1)-M )*cnt + s;
        }
    }
    cout<<ans<<"\n";
}

Submission Info

Judge Result