GYM102798C - Rencontre

来源：CCPC2020 · 威海

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

知识点：树形DP、组合数学、古典概型、贡献

难度：紫、银牌

题意

给出一棵 n 个节点的树，
再给出三个点集，点集中的点表示树上的点，这三个点集中的点互不相同。
现在从这三个点集中各随机选出一个点。有三个人分别从这三个点出发，前往同一个会合点，求这三个人走过距离总和的期望。

思路

考虑古典概型 $ans=\frac{所有情况对答案的贡献的加和}{情况总数}$

所有情况总数怎么算？

三个点集累乘。

所有情况对答案的贡献的加和怎么算？

所有情况对答案的贡献一定涉及到边权。
所以，从边下手。
每条边对总和的贡献是多少？
对于树上的某条边，他对总和的贡献为

$len \times 该边下方点集1的点的数量\times该边上方点集2的点的数量\times该边上方点集3的点的数量$

$+len \times 该边上方点集1的点的数量\times该边下方点集2的点的数量\times该边下方点集3的点的数量$

$+len \times 该边下方点集2的点的数量\times该边上方点集1的点的数量\times该边上方点集3的点的数量$

$+len \times 该边上方点集2的点的数量\times该边下方点集1的点的数量\times该边下方点集3的点的数量$

$+len \times 该边下方点集3的点的数量\times该边上方点集1的点的数量\times该边上方点集2的点的数量$

$+len \times 该边上方点集3的点的数量\times该边下方点集1的点的数量\times该边下方点集2的点的数量$

可以发现，对于一条边，以上这六种情况相互独立。

代码

#include <cstdio>
#include <iostream>
#include <vector>
const int N	= 1e6+10;
using namespace std;

int dp[N][5];
int cnti[5];
vector<int> G[N],W[N];
int n;
double sum=0,mul=1; 

void DFS(int cur,int pre)
{
	for (int i=0; i<G[cur].size(); i++)
	{
		int nxt = G[cur][i];
		int len = W[cur][i];
		if(nxt==pre)continue;
		
		DFS(nxt, cur);
		
		sum += 1.0 * len * dp[nxt][1] * (cnti[2]-dp[nxt][2]) * (cnti[3]-dp[nxt][3]);
		sum += 1.0 * len * (cnti[1]-dp[nxt][1]) * dp[nxt][2] * dp[nxt][3];
		
		sum += 1.0 * len * dp[nxt][2] * (cnti[1]-dp[nxt][1]) * (cnti[3]-dp[nxt][3]);
		sum += 1.0 * len * (cnti[2]-dp[nxt][2]) * dp[nxt][1] * dp[nxt][3];
		
		sum += 1.0 * len * dp[nxt][3] * (cnti[1]-dp[nxt][1]) * (cnti[2]-dp[nxt][2]);
		sum += 1.0 * len * (cnti[3]-dp[nxt][3]) * dp[nxt][1] * dp[nxt][2];
		
		
		for(int j=1;j<=3;j++)
		{
			dp[cur][j] += dp[nxt][j];
		}
	}
}


void Solve()
{
	DFS(1, 0);
	printf("%lf\n",sum/mul);
}

int main()
{
	scanf("%d",&n);
	for (int i=1; i<=n-1; i++)
	{
		int u,v,w;
		scanf("%d %d %d",&u,&v,&w);
		G[u].push_back(v);
		W[u].push_back(w);
		G[v].push_back(u);
		W[v].push_back(w);
	}
	
	for (int i=1; i<=3; i++)
	{
		scanf("%d",&cnti[i]);
		mul *= 1.0*cnti[i];
		for(int j=1;j<=cnti[i];j++)
		{
			int x;
			scanf("%d",&x);
			dp[x][i]+=1;
		}
	}
	
	Solve();
	
	return 0;
}

题解 | #CCPC Rencontre# 超详细题解

GYM102798C - Rencontre

题意

思路

所有情况总数怎么算？

所有情况对答案的贡献的加和怎么算？

代码