题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6567
题目大意
给你两棵树,让你在两棵树之间加一条边,使得两棵树联通且任意两结点之间的距离之和最短
就是最小化这个式子
$$
\sum_{i=1}^n\sum_{j=i+1}^ndis\left(i,j\right)
$$
思路
首先分别对两棵树$Tree_A$和$Tree_B$,我们在$Tree_A$中找一个点$S_A$,使得$Tree_A$中所有点到$S_A$的距离之和最小,同理在$Tree_B$中找到$S_B$,将这两个点连接起来,就是符合题目要求的边.
因为两棵树之间只有这一条边相连,那么$Tree_A$中的点要去$Tree_B$,就必须经过$S_A,S_B$,又因为$S_A,S_B$是各自的树里面的结点距离之和最小的,那么把它们连起来就是符合题意的
(其实$S_A,S_B$就是树的重心)
那么怎样找$S_A$呢,首先以任意一个顶点为根,假设以$1$为根,维护两个数组$sum[i]$,表示$i$的子节点到$i$的的距离之和,$sum\_num[i]$表示$i$的子节点的个数,现在以$1$为根做一遍DFS可以得到这两个数组。
然后开始换根,假设现在的根是$now$, $v$是$now$的子节点,那么当根从$now$变到$v$时
- $sum\_num[now]-=(sum\_num[v]+1)$即$v$及$v$的子节点不再是$now$的子节点,遂减去
- $sum[now]-=(sum[v]+sum\_num[v]+1)$即$v$及$v$的子节点不再走到$now$,这部分的权值是它们走到$v$的权值加上它们再走一步走到$now$,再走一步走到$now$的值就是结点个数$*1$,即$(sum[v]+sum\_num[v]+1)$
- $sum\_num[v]+=sum\_num[now]+1$即$now$及$now$的子节点变成了$v$的子节点,注意:这里的$sum\_num[now]$已经是经过上面变换之后的
- $sum[v]+=(sum[now]+sum\_num[now]+1)$即$now$及$now$的子节点将会走到$v$,这部分的权值是它们走到$now$的权值加上它们再走一步走到$v$,再走一步走到$v$的值就是结点个数$*1$,即$(sum[now]+sum\_num[now]+1)$,注意:这里的关于$now$的数组已经是经过前两步变换过的
然后遍历树中的所有结点我们就能得到以$S_A$为根,最小的$sum[S_A]$
找出$S_A,S_B$之后就可以计算题目中的那个式子了:
$Tree_A$中的每一个点都要与$Tree_B$中的每一个点计算距离,那么首先$Tree_A$中的每一个点要先走到$S_B$,距离就是$sum[S_A]+Tree_A$中结点个数,这个式子的含义就是$Tree_A$中所有点先走到$S_A$,再走一步到$S_B$
又因为$Tree_B$中有$N$个结点,所以$Tree_A$中的每一个点都要走$N$次去$S_B$这条路,所以要乘以$N$
然后$S_B$到$Tree_B$中所有点的距离之和是$sum[S_B]$,这个值会被计算$Tree_A$中结点个数次,所以要乘以$Tree_A$中的结点个数
最后的结果就是
$$
(sum[S_A]+sum\_num[S_A]+1)*(sum\_num[S_B]+1)+sum[S_B]*(sum\_num[S_A]+1)
$$
其中$sum\_num[S_A]+1$和$sum\_num[S_B]+1$就是$Tree_A$和$Tree_B$中的结点个数.
上面是两棵树之间点的距离之和,最后再加上两棵树各自内部的点之间的距离之和就行了,这个可以再换根的时候就得到换根时每一个点都作为根计算过$sum[i]$,只需要将每个$sum[i]$累加起来最后除以2就行了
AC代码
1 |
|