题解：AT_abc401_f [ABC401F] Add One Edge 3

#include <bits/stdc++.h>
#define int long long
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f;
inline int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const int N=2e5+10;
struct graph{
    int n,d,s,t,a[N];
    vint G[N];
    void add(int u,int v){
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int dis[N],vis[N];
    void bfs(int s){
        memset(dis,0,sizeof dis),memset(vis,0,sizeof vis);
        queue<int> Q;
        Q.push(s);
        while(!Q.empty()){
            int u=Q.front();Q.pop();
            vis[u]=1;
            for(int v:G[u]){
                if(vis[v]) continue;
                dis[v]=dis[u]+1;Q.push(v);
            }
        }
    }
    int get_d(){
        bfs(1);
        s=max_element(dis+1,dis+n+1)-dis;
        bfs(s);
        t=max_element(dis+1,dis+n+1)-dis;
        return d=dis[t];
    }
    void get_a(){
        bfs(s);
        memcpy(a,dis,sizeof a);
        bfs(t);
        rep(i,1,n) a[i]=max(a[i],dis[i]);
    }
}G1,G2;
int d1,d2,d,pre[N];
signed main(){
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    G1.n=read();
    for(int i=1,u,v;i<G1.n;++i){
        u=read(),v=read();
        G1.add(u,v);
    }
    G2.n=read();
    for(int i=1,u,v;i<G2.n;++i){
        u=read(),v=read();
        G2.add(u,v);
    }
    d1=G1.get_d(),d2=G2.get_d();
    d=max(d1,d2);
    G1.get_a(),G2.get_a();
    int ans=0;
    sort(G2.a+1,G2.a+G2.n+1);
    rep(i,1,G2.n) pre[i]=pre[i-1]+G2.a[i];
    for(int i=1;i<=G1.n;++i){
        int k=G1.a[i]+1;
        int pos=lower_bound(G2.a+1,G2.a+G2.n+1,d-k)-G2.a;
        if(pos==G2.n+1) ans+=d*G2.n;
        else{
            ans+=(pos-1)*d;
            ans+=pre[G2.n]-pre[pos-1]+(G2.n-pos+1)*(1+G1.a[i]);
        }
    }
    cout<<ans<<endl;
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}