1 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int N = 2e4 + 4; vector< pair<int, int> > G[N]; int n, ans; int siz[N], all, rt, rtmaxsiz; int dis[N], t[4]; bool del[N]; void getroot(int x, int xfa) { siz[x] = 1; int xmaxsiz = 0; for (auto i:G[x]) if (i.first != xfa && !del[i.first]){ getroot(i.first, x); siz[x] += siz[i.first]; xmaxsiz = max(xmaxsiz, siz[i.first]); } xmaxsiz = max(xmaxsiz, all - siz[x]); if (xmaxsiz < rtmaxsiz) rtmaxsiz = xmaxsiz, rt = x; } void getdis(int x, int xfa) { t[dis[x]]++; for (auto i:G[x]) if (i.first != xfa && !del[i.first]){ dis[i.first] = (dis[x] + i.second)%3; getdis(i.first, x); } } int calc(int x,int w) { t[0]=t[1]=t[2]=0; dis[x]=w; getdis(x, 0); return t[1]*t[2]*2 + t[0]*t[0]; } void divide(int x) { ans+=calc(x,0); del[x] = true; for (auto i:G[x]) if (!del[i.first]){ ans-=calc(i.first,i.second); all=rtmaxsiz=siz[i.first];getroot(i.first, x);getroot(rt, x); divide(rt); } } int gcd(int a,int b){ return b==0?a:gcd(b,a%b);} int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin >> n ; for (int i = 2, x, y, w; i <= n; i++) { cin >> x >> y >> w; w%=3; G[x].push_back({y, w}); G[y].push_back({x, w}); } ans = 0; all=rtmaxsiz=n;getroot(1, 0);getroot(rt, 0); divide(rt); int g= gcd(ans,n*n); cout << ans/g << "/" << n*n/g << "\n" ; return 0; }
- 1
信息
- ID
- 3817
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 22
- 已通过
- 8
- 上传者