CCPC-2020威海 C. Rencontre

题目链接：https://codeforces.com/gym/102798/problem/C

分析

三个人选出来的情况都是等概率的，所以答案就是每种情况的路程相加的和除以情况数。
总情况数就是三个人可选的点数相乘。
至于路程总和，对于每条边来说，若其一侧有一个人的点，另一侧有另外两个人的点，那么条边肯定是要被选择的，至于被选到的次数，一定是一侧有一个人的点，另一侧有两个，总共有六种情况，即可算出。
注意每种情况路程总和可能会爆longlong，可以开__int128。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define lson (k << 1)
#define rson (k << 1 | 1)const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const ll P = 1e9 + 7;int n;
vector<pii> g[N];
int f[5][N], s[5][N], k[5];
__int128 sum;void dfs(int u, int fa)
{
    for(int i=1;i<=3;i++) if(f[i][u]) s[i][u]++;for(int i=0;i<g[u].size();i++){
    int v = g[u][i].first;if(v == fa) continue;int w = g[u][i].second;dfs(v, u);s[1][u] += s[1][v];s[2][u] += s[2][v];s[3][u] += s[3][v];sum += 1ll * w * s[1][v] * (k[2] - s[2][v]) * (k[3] - s[3][v]);sum += 1ll * w * s[2][v] * (k[1] - s[1][v]) * (k[3] - s[3][v]);sum += 1ll * w * s[3][v] * (k[1] - s[1][v]) * (k[2] - s[2][v]);sum += 1ll * w * (k[1] - s[1][v]) * s[2][v] * s[3][v];sum += 1ll * w * (k[2] - s[2][v]) * s[1][v] * s[3][v];sum += 1ll * w * (k[3] - s[3][v]) * s[1][v] * s[2][v];}
}int main() {
    scanf("%d",&n);for(int i=1;i<n;i++){
    int u, v, w;scanf("%d%d%d",&u,&v,&w);g[u].push_back({
    v, w});g[v].push_back({
    u, w});}ll tot = 1;for(int i=1;i<=3;i++){
    int x;scanf("%d",&k[i]);tot *= k[i];for(int j=1;j<=k[i];j++){
    scanf("%d",&x);f[i][x] = 1;}}dfs(1, 0);printf("%.10lf",1.0 * sum / tot);return 0;
}