- 1#include 2#include 3#include 4#include 5#include 6 using namespace std;
- 7 int rd() {
- int z = 0,
- mk = 1;
- char ch = getchar();
- 8
- while (ch < '0' || ch > '9') {
- if (ch == ' - ') mk = -1;
- ch = getchar();
- }
- 9
- while (ch >= '0' && ch <= '9') {
- z = (z << 3) + (z << 1) + ch - '0';
- ch = getchar();
- }
- 10
- return z * mk;
- 11
- }
- 12 int gcd(int x, int y) {
- return y ? gcd(y, x % y) : x;
- }
- 13 struct ddd {
- int nxt,
- y,
- v;
- }
- e[41000];
- int lk[21000],
- ltp = 0;
- 14 inline void ist(int x, int y, int z) {
- e[++ltp].nxt = lk[x],
- lk[x] = ltp,
- e[ltp].y = y,
- e[ltp].v = z;
- }
- 15 int n;
- 16 int tt = 0,
- rt = 0;
- 17 bool vstd[21000];
- 18 int f[21000],
- sz[21000];
- 19 int dp[21000],
- cnt[3];
- 20 int ans = 0;
- 21 void gtrt(int x, int fth) {
- 22 sz[x] = 1,
- f[x] = 0;
- 23
- for (int i = lk[x]; i; i = e[i].nxt) if (e[i].y != fth && !vstd[e[i].y]) {
- 24 gtrt(e[i].y, x);
- 25 sz[x] += sz[e[i].y];
- f[x] = max(f[x], sz[e[i].y]);
- 26
- }
- 27 f[x] = max(f[x], tt - sz[x]);
- 28
- if (f[x] x; 29
- }
- 30 void gtdp(int x, int fth) {
- 31++cnt[dp[x]];
- 32
- for (int i = lk[x]; i; i = e[i].nxt) if (e[i].y != fth && !vstd[e[i].y]) 33 dp[e[i].y] = (dp[x] + e[i].v) % 3,
- gtdp(e[i].y, x);
- 34
- }
- 35 int cclt(int x, int y) {
- 36 cnt[0] = cnt[1] = cnt[2] = 0;
- dp[x] = y;
- 37 gtdp(x, 0);
- 38
- return cnt[1] * cnt[2] * 2 + cnt[0] * cnt[0];
- 39
- }
- 40 void dfs(int x) {
- 41 ans += cclt(x, 0);
- vstd[x] = true;
- 42
- for (int i = lk[x]; i; i = e[i].nxt) if (!vstd[e[i].y]) {
- 43 ans -= cclt(e[i].y, e[i].v);
- 44 rt = 0,
- tt = sz[e[i].y];
- gtrt(e[i].y, 0),
- dfs(rt);
- 45
- }
- 46
- }
- 47 int main() { //freopen("ddd.in","r",stdin);
- 48 memset(vstd, 0, sizeof(vstd));
- 49 cin >> n;
- 50 int l,
- r,
- v;
- 51
- for (int i = 1; i3, ist(l, r, v), ist(r, l, v); 52 tt = n, f[0] = n; gtrt(1, 0), dfs(rt); 53 int tmp = gcd(ans, n * n); 54 cout < ' / ' < endl; 55
- return 0; 56
- }
来源: http://www.bubuko.com/infodetail-1983757.html