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
| #include<cstdio>
#include<ctime>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define clear(a) memset(a, 0, sizeof(a))
using namespace std;
const int MAXN=40000 * 2 + 5, INF=0x3f3f3f3f;
struct ed {
int to,w,nex;
} e[MAXN];
int dep[MAXN];
int newp, root, sizeTot,newd;
int n, m, k;
int ans;
int head[MAXN], dist[MAXN];
int treeSize[MAXN], sonLargest[MAXN]={INF};
bool v[MAXN];
void lineAdd (int p1, int p2, int w);
void getG (int v, int fa);
void getDep (int p, int fa, int l);
void solve (int u);
int calc (int p, int de);
int gcd (int p1, int p2) {return (p2 % p1 == 0) ? p1 : gcd(p2 % p1, p1);}
int main(void) {
#ifndef ONLINE_JUDGE
long _begin_time = clock();
freopen("in.txt","r",stdin);
freopen("out.txt", "w", stdout);
#endif
scanf("%d", &n);
sizeTot = sonLargest[0] = n;
for (int i = 1; i < n; ++i) {
int p1, p2, w;
scanf("%d%d%d", &p1, &p2, &w);
lineAdd(p1, p2, w);
lineAdd(p2, p1, w);
}
getG(1, 0);
solve(root);
int fenMu = n * n;
int g = gcd(ans, fenMu);
printf("%d/%d\n", ans / g, fenMu / g);
#ifndef ONLINE_JUDGE
long _end_time = clock();
cout << "time = " << _end_time - _begin_time << "ms" <<endl;
#endif
return 0;
}
void lineAdd(int p1, int p2, int w) {
++newp;
e[newp].w = w;
e[newp].to = p2;
e[newp].nex = head[p1];
head[p1] = newp;
}
void getG(int p, int fa) {
treeSize[p] = 1;
sonLargest[p] = 0;
for (int i = head[p]; i; i = e[i].nex) {
int y = e[i].to;
if (y != fa && (v[y] == 0)) {
getG(y, p);
treeSize[p] += treeSize[y];
sonLargest[p] = max(sonLargest[p], treeSize[y]);
}
}
sonLargest[p] = max(sonLargest[p], sizeTot - treeSize[p] + 1);
if (sonLargest[p] < sonLargest[root]) root = p;
}
void getDep(int p, int fa, int l) {
++dep[l % 3];
for (int i = head[p]; i; i = e[i].nex) {
int y = e[i].to;
if (y !=fa && (!v[y])) {
getDep(y, p, (l + e[i].w) % 3);
}
}
}
void solve(int u) {
v[u] = 1;
ans += calc(u, 0);
for (int i = head[u]; i; i = e[i].nex) {
int y = e[i].to;
if (!v[y]) {
ans -= calc(y, e[i].w);
sonLargest[0] = sizeTot = treeSize[u];
root = 0;
getG(y, 0);
solve(root);
}
}
}
int calc (int p, int de) {
dep[0] = dep[1] = dep[2] = 0;
getDep(p, 0, de);
int ans = dep[0] * dep[0] + dep[1] * dep[2] * 2;
return ans;
}
|
右儿子路径求解
