1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LL long long
#define MAXN 9
#define MS 20009
LL n,m;
struct node{
int to,val;
};
vector<node > vc[MS];
LL ans,sum;
int rt,tr_size;
int sz[MS],w[MS];
int del[MS];
int dis[MS];
int ext[MAXN];
int dismap[MAXN];
void get_rt(int u,int f){
sz[u] = 1;
w[u] = 0;
for(auto &nb:vc[u]){
int v = nb.to;
if(v != f && !del[v]){
get_rt(v,u);
sz[u] += sz[v];
w[u] = max(w[u],sz[v]);
}
}
w[u] = max(w[u],tr_size-sz[u]);
if(w[u] < w[rt]) rt = u;
}
void get_dis(int u,int f){
dismap[dis[u]%3]++;
for(auto &nb:vc[u]){
int v = nb.to;
int val = nb.val;
if(v != f && !del[v]){
dis[v] = ( dis[u]+val ) % 3;
get_dis(v,u);
}
}
}
void cal(int u){
ext[0]++;
for(auto &nb:vc[u]){
int v = nb.to;
int val = nb.val;
if(!del[v]){
for(int i=0;i<3;i++) dismap[i] = 0;
dis[v] = val % 3;
get_dis(v,u);
for(int i=0;i<3;i++){
ans += dismap[i]*ext[(3-i)%3]*2;
}
for(int i=0;i<3;i++){
ext[i] += dismap[i];
}
}
}
for(int i=0;i<3;i++) ext[i] = 0;
}
void divide(int u){
del[u] = 1;
cal(u);
for(auto &nb:vc[u]){
int v = nb.to;
if(!del[v]){
w[rt = 0] = tr_size = sz[v];
get_rt(v,0);
get_rt(rt,0);
divide(rt);
}
}
}
void solve(){
cin >> n;
for(int i=2;i<=n;i++){
int u,v,val;
cin >> u >> v >> val;
val %= 3;
vc[u].push_back({v,val});
vc[v].push_back({u,val});
}
ans = n ,sum = n*n;
w[rt = 0] = tr_size = n;
get_rt(1,0);
get_rt(rt,0);
divide(rt);
LL t = __gcd(ans,sum);
ans /= t ,sum /= t;
cout << ans << "/" << sum << "\n";
}
int main(){
ios::sync_with_stdio(false);
int ce;
ce = 1;
while(ce--){
solve();
}
return 0;
}
|
