P2634 [国家集训队]聪聪可可

Miku

可以用树上dp解决

(dp_{i,j})表示以i为根的子树在模三意义下到i的距离为j的点有几个

然后根据乘法原理搞一波

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int x,y,z;
const int maxn=200004;
int head[maxn+10];
int p;
int du[maxn];
int ans;
int dp[maxn][5];
struct e{
	int f;
	int to;
	int ne;
	int w;
} ed[maxn];
void add(int f,int t,int w){
	p++;
	ed[p].ne=head[f];
	ed[p].f=f;
	ed[p].w=w;
	ed[p].to=t;
	head[f]=p;
	return ;
}
void dfs(int now,int f){
	dp[now][0]=1;
	for(int i=head[now];i;i=ed[i].ne){
		if(ed[i].to!=f){
			dfs(ed[i].to,now);
		for(int j=0;j<=2;++j){
			ans+=dp[now][(3-(j+ed[i].w%3+3)%3)%3]*dp[ed[i].to][j]*2;
			//当前点也可以和now子树上之前的点门组合
			//只要距离合法 
		}	
		for(int j=0;j<=2;++j){
			dp[now][((j+ed[i].w)%3+3)%3]+=dp[ed[i].to][j];
		}
	}
	}
	return ;
}
int gcd(int x,int y){
	return y==0 ? x :gcd(y,x%y);
}
int anss;
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	anss=n*n;
	dfs(1,0);
	ans+=n;//选自己也可以哦 
	cout<<ans/gcd(ans,anss)<<"/"<<anss/gcd(ans,anss);
	return 0;
}