洛谷P2634 [国家集训队]聪聪可可(点分治)

左手的ㄟ右手 2023-08-17 17:21 104阅读 0赞

# 聪聪可可 #

[题目传送门][Link 1]

## 解题思路 ##

点分治。分别统计(各个点到根的距离%3)的值为0，1，2的个数，然后统计不在同一颗子树中余数相加再%3的值为0的个数x，因为两个人可以选同一个点，所以x+n即为路径为3倍数的点对的个数。概率即为(x+n)/(n\*n)。

## 代码如下 ##

#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; inline int read(){ int res = 0, w = 0; char ch = 0; while(!isdigit(ch)){ w |= ch == '-', ch = getchar(); } while(isdigit(ch)){ res = (res << 3) + (res << 1) + (ch ^ 48); ch = getchar(); } return w ? -res : res; } template <typename A, typename B, typename C> inline A fpow(A x, B p, C lyd){ A ans = 1; for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd; return ans % lyd; } ll get_inv(ll b, ll mod){ return fpow(b, mod - 2, mod); } const int N = 20005; struct T{ int r, w; T(int r, int w): r(r), w(w){} }; vector<T> g[N]; int rt, num, n, sum; int siz[N]; bool vis[N]; void find_root(int x, int fa) { siz[x] = 1; int max_son = 0; for(int i = 0; i < g[x].size(); i ++){ int r = g[x][i].r; if(r == fa || vis[r]) continue; find_root(r, x); siz[x] += siz[r]; max_son = max(max_son, siz[r]); } max_son = max(max_son, sum - siz[x]); if(max_son < num){ num = max_son; rt = x; } } int d[N], b[N]; vector<int> vec; void get_dis(int x, int fa, int s) { for(int i = 0; i < g[x].size(); i ++){ int r = g[x][i].r; if(r == fa || vis[r]) continue; d[r] = (d[x] + g[x][i].w) % 3, b[r] = s; vec.push_back(r); get_dis(r, x, s); } } int cnt[N][3], ans; int e[3]; void calc() { memset(cnt, 0, sizeof(cnt)); memset(e, 0, sizeof(e)); for(int i = 0; i < vec.size(); i ++){ cnt[b[vec[i]]][d[vec[i]] % 3] ++; e[d[vec[i]] % 3] ++; } for(int i = 0; i < vec.size(); i ++){ int t = d[vec[i]] % 3; for(int j = 0; j < 3; j ++){ if((t + j) % 3 == 0) ans += e[j] - cnt[b[vec[i]]][j]; } } } void dfs(int x) { num = n; find_root(x, 0); int t = rt; vis[t] = true; vec.clear(); vec.push_back(t); d[t] = b[t] = 0; for(int i = 0; i < g[t].size(); i ++){ int r = g[t][i].r; if(!vis[r]){ d[r] = g[t][i].w % 3, b[r] = r; vec.push_back(r); get_dis(r, t, r); } } calc(); for(int i = 0; i < g[t].size(); i ++){ int r = g[t][i].r; if(!vis[r]){ sum = siz[r]; dfs(r); } } } int main() { scanf("%d", &n); for(int i = 1; i < n; i ++){ int x, y, w; scanf("%d%d%d", &x, &y, &w); g[x].push_back(T(y, w)); g[y].push_back(T(x, w)); } sum = n; dfs(1); int b = n * n; ans += n; int w = __gcd(ans, b); printf("%d/%d\n", ans / w, b / w); return 0; }

转载于:https://www.cnblogs.com/whisperlzw/p/11545274.html

[Link 1]: https://www.luogu.org/problem/P2634