CF1060E-Sergey and Subway
题目大意：给定一棵无向树，在保留原有边的情况下将所有距离为2的点之间再连一条无向边，构成一张图。问这张图所有点对之间的最短距离之和是多少。
注意到：新图上任意两点之间的最短距离是原树上这两点间最短距离除以二再向上取整。
偶数除以二向上取整的值相当于直接除以二，而奇数除以二向上取整相当于原数加上一再除以二。所以要求的值就是(原树上任意两点间路径长度之和+原树上长度为奇数的路径数量)/2。
长度为奇数的路径数量怎么求？注意到：任意点到与它深度相同的点的路径长度一定是偶数，因此深度奇偶不相同的两点之间的路径长度一定是奇数。根据乘法原理，长度为奇数的路径数量=深度为奇数的点数×深度为偶数的点数。
原树上任意两点间路径长度之和怎么求？不难发现：对于树上的任意边，它两边的结点要连接，一定会经过这条边。因此原树上任意两点间路径长度之和就是所有边两边的点数相乘。具体的做法是：已知以i为根的子树的节点数dp[i]，那么i与它父亲相邻的这条边的贡献就是dp[i] * (n - dp[i])。
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
| #include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> son[200005];
int sumd[2], dp[200005], res, n;
bool vis[200005];
void sol(int root, int dpth)
{
vis[root] = 1;
dp[root] = 1;
sumd[dpth]++;
for (int i = 0; i < son[root].size(); i++)
{
int s = son[root][i];
if (!vis[s])
{
sol(s, dpth ^ 1);
dp[root] += dp[s];
res += dp[s] * (n - dp[s]);
}
}
}
signed main()
{
int i, u, v;
scanf("%lld", &n);
for (i = 1; i < n; i++)
{
scanf("%lld%lld", &u, &v);
son[u].push_back(v);
son[v].push_back(u);
}
sol(1, 0);
int js = sumd[0] * sumd[1];
printf("%lld", res + js >> 1);
return 0;
}
|