题意
给出一棵\(n\)个点的带权无根树, 给出三个点的集合. 在每个集合任取一点, 在树上寻找新的一个点使得该点到三点的路径和最短. 求路径和期望
$ 1 n ^5,1 w $
题解
首先考虑这样一个问题: 给出树上三点\(a,b,c\), 求这三点汇聚到一点\(v\)的最短路径(设为\(f(a,b,c)\)) \[
f(a,b,c) = \min\{v\in V |dis(a,v) + dis(b,v) + dis(c,v)\}
\]
如上图所示, \(a,b,c\)为\(3,4,5\). 观察易得汇合点\(v\)为\(2\), 即\(a,b,c\)的LCA中深度最深的那个. 此时\(a,b\space a,c \space b,c\)间的每条边都恰好经过一次, 即: \[
f(a,b,c) = \frac{1}{2}(dis(a,b) + dis(a,c) + dis(b,c))
\] 由期望的性质\(E(X + Y) = E(X) + E(Y)\), 我们可以分别计算两个集合\(j,k\)中各点的距离和. 通过一遍DFS来计算子树\(u\)中属于集合\(i\)的节点个数\(num[u][i]\), 再对每条边分别统计贡献\(g\). 设\(cnt_i\)为集合\(i\)的大小. \[
g(e_i,j,k) = ((cnt_i - num[u][j])*num[u][k] + (cnt_k - num[u][k])*cnt_j)*e_i.w
\] 答案即为 \[
\sum_{j = 1}^3 \sum_{k = j+1}^3\frac{\sum_{i = 1}^{n-1}g(e_i,j,k)}{2\cdot cnt_j \cdot cnt_k}
\]
代码
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int long long
#define endl '\n'
const int maxn = 2e5+10;
const int maxm = 4e5+10;
int head[maxn],cnt,use[maxn][4],num[maxn][4];
int n;
ll sum[4][4];
struct Edge{
int f,t,w,next;
Edge(int f = 0,int t = 0,int w = 0,int next = 0):f(f),t(t),w(w),next(next){}
}edge[maxm];
void addedge(int f,int t,int w){
edge[cnt] = Edge(f,t,w,head[f]);
head[f] = cnt++;
}
void DFS(int u,int fa){
for(int i = 1;i <= 3;i++)if(use[u][i])num[u][i] = 1;
for(int i = head[u];~i;i = edge[i].next){
int v = edge[i].t,w = edge[i].w;
if(v == fa)continue;
DFS(v,u);
for(int j = 1;j <= 3;j++){
for(int k = j+1;k <= 3;k++){
sum[j][k] += (num[0][j] - num[v][j])*num[v][k]*w;
sum[j][k] += (num[0][k] - num[v][k])*num[v][j]*w;
}
}
for(int j = 1;j <= 3;j++)num[u][j] += num[v][j];
}
}
signed main(){
cout.setf(ios::fixed,ios::floatfield);
cout.precision(10);
ios::sync_with_stdio(0);
cin.tie(0);
memset(head,-1,sizeof(head));
cin >> n;
for(int i = 1;i < n;i++){
int f,t,w;
cin >> f >> t >> w;
addedge(f,t,w);
addedge(t,f,w);
}
for(int i = 1;i <= 3;i++){
int m;
cin >> m;
num[0][i] = m;
for(int j = 1;j <= m;j++){
int x;
cin >> x;
use[x][i] = 1;
}
}
DFS(1,-1);
ld ans = 0;
for(int i = 1;i <= 3;i++){
for(int j = i+1;j <= 3;j++)ans += (double)sum[i][j]/num[0][i]/num[0][j]/2;
}
cout << ans << endl;
return 0;
}
|
PS: 当时我这题题意转述的时候锅了, 导致队友直接一个点分治敲上去, 敲完才发现不对劲=-= 不然这题是有可能做出来的