CCPC-2020威海 C. Rencontre

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

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

#include
using namespace std;
typedef long long ll;
typedef pair 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 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					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/4752139.html