传送门：https://codeforces.ml/gym/102798/problem/C
题意
给一棵树，树上的点分为三种。 首先分别在三种点中随机选择一点a,b,c，然后找到一个合适的v，使得 $$f=min(dis(a,v)+dis(b,v)+dis(c,v))$$
求出f的期望。
思路
当a,b,c确定下来，那么v也会确定下来，因为min，所以我们围绕a,b,c展开。
数学上可以推出$min(dis(a,v)+dis(b,v)+dis(c,v))=\frac{1}{2}(dis(a,b)+dis(b,c)+dis(c,a))$ 这样我们就不需要考虑v的存在，而怎么求dis呢？
显然dis中的点是在树上的，所以总贡献为 $$\frac{\sum_{x\in a}\sum_{y\in b}dis(x,y)}{ab}+\frac{\sum_{x\in c}\sum_{y\in b}dis(x,y)}{cb}+\frac{\sum_{x\in a}\sum_{y\in c}dis(x,y)}{ac}$$
a，b，c的个数输入的时候就知道了，那么就是求所有的dis，即树上任意两点距离和。
很多人都知道，树上任意两点之间距离就是dfs一遍树，对于一条边$ans+=(n-siz[v])*siz[v]*w$
这里同如此，只不过是进化版，是要在三个块中选择不同点求任意距离和。 没关系，设siz[u][1/2/3]表示以u为根节点的子树中，1/2/3种类的点有多少个。
然后根据siz大小循环转移即可。
难点应该就是怎么在不同块中求贡献了。首先dfs1预处理出全部的siz，再dfs2对边求贡献。
Code
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
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
struct Edge {
int v;
ll w;
};
vector<Edge> g[N];
ll cnt[4], siz[N][4];;
double ans;
void dfs1(int u, int fa) {
for(auto e : g[u]) {
int v = e.v;
if(v == fa) continue;
dfs1(v, u);
for(int i = 1;i <= 3; i++) {
siz[u][i] += siz[v][i];
}
}
}
void dfs2(int u, int fa) {
for(auto e : g[u]) {
int v = e.v;
if(v == fa) continue;
dfs2(v, u);
for(int i = 1;i <= 3; i++) {
for(int j = 1;j <= 3; j++) {
if(i == j) continue;
ans += 1.0 * ((siz[1][i] - siz[v][i]) * siz[v][j] * 1.0 * e.w / (cnt[i] * cnt[j]) / 2.0);
}
}
}
}
void solve() {
int n; cin >> n;
for(int i = 1;i < n; i++) {
int u, v; ll w; cin >> u >> v >> w;
g[u].push_back(Edge{v, w});
g[v].push_back(Edge{u, w});
}
for(int i = 1;i <= 3; i++) {
cin >> cnt[i];
for(int j = 1;j <= cnt[i]; j++) {
int x; cin >> x;
siz[x][i]++;
}
}
dfs1(1, -1);
dfs2(1, -1);
cout << fixed << setprecision(12) << ans << endl;
}
signed main() {
solve();
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/03/06/2020-ccpc-weihai-c/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！