我是看了这位大佬的博客，感谢大佬他的博客

题目描述：有两颗树，需要在这两棵树之间添加一条边，这样就变成了一棵树，求这棵树任意两点之间的最小距离和

即$$\sum ^{N}{i=1}\sum ^{N}{j=i+1}dis\left( i,j\right)$$

解题思路：首先考虑，我们要在哪两个点之间添加一条边呢？这个点实际上就是树的重心，树的重心是这样定义的：树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡（引自百度百科）在这个问题中，也是找到一个点，使得这棵树上的其他点到这个点的距离和最小，这个点即这棵树的重心。

那么怎样找重心呢？我们定义sum[i]:一颗树中其他点到i点的距离和 sum_num[i]:为i的子节点数。任意选取一个点为根，这两个数组可以用跑一次DFS求出来，找重心就是就是找到一个合适的根，使得sum[根]最小，我们可以利用换根来实现。假设u是根，v是u的紧邻子节点，我们可以通过依次执行下面的四个步骤实现将根换为v,你可以将图画出来，这样容易理解

1.sum[u]-=(sum[v]+sum_num[v]+1)其中sum_num[v]+1是因为v的子节点及本身到u都还得加上一个距离，v的子节点本来是到v的，现在到u，每一个子节点到u得加上u->v这条边

2.sum_num[u]-=(sum_num[v]+1),将u的子节点数减去v的子节点数及其本身

3.sum[v]+=(sum[u]+sum_num[u]+1)理解和第一个步骤一样

4.sum_num[v]+=(sum_num[u]+1),理解和第二个步骤一样

用DFS将所有可能为根的点跑一遍，用root1,root2,sum_root1,sum_root2记录找到的重心和其他点到重心的距离和

找到两颗树的重心实现连接之后，我们就可以求任意两点之间的距离和了。求之前tree1任意两点间的距离和可以在换根的同时将每一个点作为根之后的sum[根]求和除以2就可以了，同样可以求得tree2中任意两点之间的距离和。然后再加上任意两点（一个在tree1中，一个在tree2中）距离和。tree1中的任意一点想要和tree2中的一点连接，势必要通过新加入的那条边,(sum[root1]+sum_num[root1]+1)(sum_num[root2]+1)，tree2中的一点与tree1中的所有点的距离和为sum[root1]+sum_num[root1]+1(这个距离是部分距离，起点是tree1中的任意一点，终点至root2,sum_num[root1]+1是tree1的节点数)，因为tree2中有(sum_num[root2]+1)个点，所以要乘以(sum_num[root2]+1)。最后还要加上sum[root2](sum_num[root1]+1),这个是因为tree1中的任意一个节点，路经root2和tree2中的所有节点距离的求和，而tree1中有sum_num[root1]+1个点，所以要乘以sum_num[root1]+1

因此这道题的答案就是

$$jie=totA/2+totB/2+(sum[rootA]+sum_num[rootA]+1)*(sum_num[rootB]+1)+(sum_num[rootA]+1)*sum[rootB]$$

代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>

using namespace std;

#define pi acos(-1.0)
#define e exp(1.0)
typedef long long ll;
const ll maxn=1e5+7;
ll N,cnt,sum[maxn],sum_num[maxn],head[maxn];
bool vis[maxn];
struct edge//链式前向星存图 
{
	ll to;
	ll next;
}E[maxn*2];//乘上2 是因为是无向边，每条边存两次 
void Add(ll u,ll v)
{
	E[cnt].to=v;
	E[cnt].next=head[u];
	head[u]=cnt++;
	return ;
}
void DFS(ll now)//求出sum[i]以及sum_num[i] 
{
	vis[now]=1;
	ll v,i;
	ll temp_sum=0,temp_sum_num=0;
	for(i=head[now];i;i=E[i].next)
	{
		v=E[i].to;
		if(!vis[v])
		{
			DFS(v);
			temp_sum+=(sum[v]+sum_num[v]+1);
			temp_sum_num+=(sum_num[v]+1);
		}
	}
	sum[now]=temp_sum;
	sum_num[now]=temp_sum_num;
	return ;
}
ll Change_root(ll now,ll &root,ll &root_sum)//换根 
{
	vis[now]=1;
	ll tot=0,i;
	tot+=sum[now];
	ll temp1=sum[now];
	ll temp2=sum_num[now];
	for(i=head[now];i;i=E[i].next)
	{
		ll v=E[i].to;
		if(!vis[v])
		{
			sum[now]-=(sum[v]+sum_num[v]+1);//换根大法四联 
			sum_num[now]-=(sum_num[v]+1);
			sum[v]+=(sum[now]+sum_num[now]+1);
			sum_num[v]+=(sum_num[now]+1);
			if(sum[v]<root_sum)//更新重心，以及各个点到重心的距离和 
			{
				root_sum=sum[v];
				root=v;
			}
			tot+=Change_root(v,root,root_sum);//为了计算各个两点之间的距离和 
			sum[now]=temp1;
			sum_num[now]=temp2; 
		}
	}
	return tot;
} 
int main()
{
// freopen(".../.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin>>N;
	ll i,j;
	cnt=1;
	for(i=1;i<=N-2;i++)
	{
		ll u,v;
		cin>>u>>v;
		Add(u,v);
		Add(v,u);
	}
	ll root_A,root_B,rootA_sum,rootB_sum;//树的重心 以及其他点到重心的距离和 
	DFS(1);
	root_A=1;//初始化 
	rootA_sum=sum[1];
	for(i=1;i<=N;i++)//找到另一颗树 
	{
		if(!vis[i])
		{
			DFS(i);
			root_B=i;//初始化 
			rootB_sum=sum[i];
			break;
		}
	}
	memset(vis,0,sizeof(vis));//这里别忘了初始化一次 
	ll tot_A=Change_root(root_A,root_A,rootA_sum);
	ll tot_B=Change_root(root_B,root_B,rootB_sum);
	ll jie=tot_A/2+tot_B/2+(rootA_sum+sum_num[root_A]+1)*(sum_num[root_B]+1)+rootB_sum*(sum_num[root_A]+1);
	cout<<jie<<endl;
	return 0;
}