题解：AT_abc401_f [ABC401F] Add One Edge 3
vanueber
·
·
题解
模拟赛题。
连接 (i,j) 两点后，新直径只可能为 d_1,d_2,dis_i+dis_j+1，其中 dis_i 为 i 在 T_1 中最远的点的距离，dis_j 为 j 在 T_2 中最远的点的距离。
直径有一条性质：从 $i$ 出发到达的最远点必定是直径的端点。那么从直径的两端出发 BFS 即可求得 $dis$。
最后固定 $i$，二分一下 $dis_i+dis_j+1$ 从什么位置开始贡献到答案，前缀和搞一搞就做完了。
```cpp
#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;
}
```