#include<cstdio>
#include<algorithm>
using namespace std;
const int N=;
int t[],head[N],son[N],f[N],d[N],root,ans,n,sum,cnt;
bool vis[N];
struct ee{int to,next,v;}e[N*];
void insert(int u,int v,int w){
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;
} int gcd(int a1,int a2)
{
int a3=a1%a2;
for(;a3;)
{
a1=a2;
a2=a3;
a3=a1%a2;
}
return a2;
} void getroot(int x,int fa){
son[x]=;f[x]=;
for (int i=head[x];i;i=e[i].next){
int v=e[i].to;
if (!vis[v]&&v!=fa){
getroot(v,x);
son[x]+=son[v];
f[x]=max(f[x],son[v]);
}
}
f[x]=max(f[x],sum-son[x]);
if (f[root]>f[x])root=x;
} void getdeep(int x,int fa){
t[d[x]]++;
for (int i=head[x];i;i=e[i].next){
int v=e[i].to;
if (v!=fa&&!vis[v]){
d[v]=(d[x]+e[i].v)%;
getdeep(v,x);
}
}
} int cal(int x,int now){
t[]=t[]=t[]=;
d[x]=now;
getdeep(x,);
return t[]*t[]*+t[]*t[];
} void work(int x){
ans+=cal(x,);
vis[x]=;
for (int i=head[x];i;i=e[i].next){
int v=e[i].to;
if (!vis[v]) {
ans-=cal(v,e[i].v);
root=;sum=son[v];
getroot(v,);
work(root);
}
}
} int main(){
scanf("%d",&n);
int u,v,w;
for (int i=;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
w%=;
insert(u,v,w);
insert(v,u,w);
}
f[]=sum=n;
root=;
getroot(,);
work(root);
int t=gcd(ans,n*n);
printf("%d/%d",ans/t,n*n/t);
}

树的点分治  首先找树的重心,把根节点设为树的重心。然后进行点分治(就是从根开始,看经过根的方案数,在把根删掉,求每棵子树)。

最新文章

  1. 关于css清除浮动,解决内容溢出的问题
  2. 在注册表中无Python3.5安装路径的情况下安装pywin32-
  3. AngularJS(一)
  4. Codeforces Round #379 (Div. 2) A. Anton and Danik 水题
  5. 企业Openvpn环境部署
  6. 【HAOI2006】【BZOJ1051】【p1233】最受欢迎的牛
  7. Sqli-labs less 38
  8. [设计模式] 15 解释器模式 Interpreter
  9. ADO.NET EF实体框架
  10. 有关XCode6(iOS8)UITableViewCell与iOS7在UITableViewCell问题
  11. opencv-阈值处理
  12. 【Alpha】第七次Daily Scrum Meeting
  13. Dockerfile基本结构
  14. OK Titlefasdf asd
  15. 关于python中loc和iloc方法
  16. 文件6. 查找替换.txt文本文件中的内容
  17. CRM--admin组件
  18. ubuntu安装jdk,maven,tomcat
  19. “ORA-06550: 第 1 行, 第 7 列”解决方法
  20. bzoj1096

热门文章

  1. SQL 调优专题总结
  2. 5.7 C和C++的关系
  3. ajax小技巧,防止多次点击发送多个请求
  4. maven 启动 报错 Fatal error compiling: 无效的目标发行版
  5. 推荐两篇Unity与Android交互的文章
  6. Java开发Maven环境配置和介绍
  7. Python--关于set
  8. C# EXCEL(.xls和.xlsx)导入到数据库
  9. Shell基础:Linux权限管理
  10. hdu----(1466)计算直线的交点数(dp)