题意
其实转化之后的题意就是求出树上有多少条路径长度是3的倍数。求答案的时候只要将这个数字除以总路径数量就行了。
思路
考虑点分治。对于当前子树，分别求出出树中每个点到根的路径长度对\(3\)取余后为\(0，1，2\)的个数。然后就可以通过\(0-0，1-2\)组合的方式，统计出答案。
然后删除当前点，继续递归下一层子树。
luogu数据较水，不找重心也能水过。
代码
/*
* @Author: wxyww
* @Date: 2019-01-30 10:56:53
* @Last Modified time: 2019-01-30 11:40:39
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<algorithm>
using namespace std;
typedef long long ll;
#define int ll
const int N = 20010;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
struct node {
int v,nxt,w;
}e[N << 1];
int head[N],ejs,n;
void add(int u,int v,int w) {
e[++ejs].v = v;e[ejs].w = w;e[ejs].nxt = head[u];head[u] = ejs;
}
int tot[4],now[4];
void dfs(int u,int father,int k) {
now[k]++;
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;if(v == father) continue;
dfs(v,u,(k + e[i].w) % 3);
}
}
ll ans = 0;
void solve(int u,int father) {
tot[0] = 1;tot[1] = tot[2] = 0;
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;if(v == father) continue;
for(int j = 0;j < 4;++j) now[j] = 0;
dfs(v,u,e[i].w % 3);
for(int j = 0;j < 4;++j) ans += tot[j] * now[(3 - j) % 3];
for(int j = 0;j < 4;++j) tot[j] += now[j];
}
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;if(v == father) continue;
solve(v,u);
}
}
signed main() {
n = read();
for(int i = 1;i < n;++i) {
int u = read(),v = read(),w = read();
add(u,v,w);add(v,u,w);
}
solve(1,0);
ans = ans * 2 + n;
int k = __gcd(ans,1ll * n * n);
printf("%lld/%lld",ans / k,1ll * n * n / k);
return 0;
}