题目大意
给你两棵树，让你在两棵树之间加一条边,使得两棵树联通且任意两结点之间的距离之和最短
就是最小化这个式子
$$
\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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
| #include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
#define wfor(i,j,k) for(i=j;i<k;++i)
#define mfor(i,j,k) for(i=j;i>=k;--i)
const ll maxn = 100005;
struct EDGE
{
ll next;
ll end;
};
ll head[maxn];
EDGE edge[maxn * 2];
ll cnt;
void add(ll beg, ll end)
{
edge[++cnt].next = head[beg];
edge[cnt].end = end;
head[beg] = cnt;
}
ll vis[maxn];
ll sum[maxn];
ll sum_num[maxn];
void dfs(ll now)
{
ll i;
ll temp_sum = 0;
ll temp_sum_num = 0;
for (i = head[now]; i; i = edge[i].next)
{
ll v = edge[i].end;
if (!vis[v])
{
vis[v] = 1;
dfs(v);
temp_sum += sum_num[v] + sum[v] + 1;
temp_sum_num += sum_num[v] + 1;
}
}
sum_num[now] = temp_sum_num;
sum[now] = temp_sum;
}
ll root_1;
ll sum_root1;
ll root_2;
ll sum_root2;
ll find_root(ll now, ll &root, ll &sum_root)
{
ll i;
ll tot = 0;
tot += sum[now];
ll temp1 = sum[now];
ll temp2 = sum_num[now];
for (i = head[now]; i; i = edge[i].next)
{
ll v = edge[i].end;
if (!vis[v])
{
vis[v] = 1;
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] < sum_root)
{
sum_root = sum[v];
root = v;
}
tot += find_root(v, root, sum_root);
sum[now] = temp1;
sum_num[now] = temp2;
}
}
return tot;
}
int main()
{
std::ios::sync_with_stdio(false);
#ifdef test
freopen("F:\\Desktop\\question\\in.txt", "r", stdin);
#endif
#ifdef ubuntu
freopen("/home/time/debug/debug/in", "r", stdin);
freopen("/home/time/debug/debug/out", "w", stdout);
#endif
ll n;
cin >> n;
ll i;
wfor(i, 0, n - 2)
{
ll u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
vis[1] = 1;
dfs(1);
root_1 = 1;
sum_root1 = sum[root_1];
wfor(i, 1, n + 1)
{
if (!vis[i])
{
vis[i] = 1;
root_2 = i;
dfs(i);
break;
}
}
sum_root2 = sum[root_2];
memset(vis, 0, sizeof(vis));
ll ans = 0;
vis[root_1] = 1;
ll temp = find_root(root_1, root_1, sum_root1);
ans += temp / 2;
vis[root_2] = 1;
temp = find_root(root_2, root_2, sum_root2);
ans += temp / 2;
ans += (sum_root2) * (sum_num[root_1] + 1) + (sum_root1 + sum_num[root_1] + 1) * (sum_num[root_2] + 1);
cout << ans << endl;
return 0;
}
|