// 模板题
#include <bits/stdc++.h> const int N = 2e4 + ; int n, now = , head[N], dis[N];
struct Node {int v, w, nxt;} G[N << ];
int size[N], maxson[N], Root;
bool vis[N];
int js[N];
int Answer;
int Size; #define gc getchar() inline int read() {
int x = ; char c = gc;
while(c < '' || c > '') c = gc;
while(c >= '' && c <= '') x = x * + c - '', c = gc;
return x;
} inline void Add(int u, int v, int w) {G[now].v = v; G[now].w = w; G[now].nxt = head[u]; head[u] = now ++;} void Getroot(int u, int fa) {
size[u] = ;
maxson[u] = ;
for(int i = head[u]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(vis[v] || v == fa) continue ;
Getroot(v, u);
size[u] += size[v];
maxson[u] = std:: max(maxson[u], size[v]);
}
maxson[u] = std:: max(maxson[u], Size - size[u]);
if(maxson[u] < maxson[Root]) Root = u;
} void Getdis(int u, int fa, int len) {
dis[u] = len; js[dis[u]] ++;
for(int i = head[u]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(vis[v] || v == fa) continue ;
Getdis(v, u, (len + G[i].w) % );
}
} int Calc(int u, int len) {
js[] = js[] = js[] = ;
Getdis(u, , len % );
return js[] * js[] * + js[] * js[];
} void Getans(int u) {
vis[u] = ;
Answer += Calc(u, );
// std:: cout << "#";
// for(int i = 1; i <= n; i ++) std:: cout << dis[i] << " ";
// std:: cout << "\n";
for(int i = head[u]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(vis[v]) continue ;
Answer -= Calc(v, G[i].w);
Root = ;
Size = size[v];
Getroot(v, u);
Getans(Root);
}
} int Gcd(int a, int b) {
return b == ? a : Gcd(b, a % b);
} int main() {
// freopen("gg.in", "r", stdin);
n = read();
for(int i = ; i <= n; i ++) head[i] = -;
for(int i = ; i < n; i ++) {
int u = read(), v = read(), w = read();
Add(u, v, w), Add(v, u, w);
}
maxson[Root] = n;
Size = n;
Getroot(, );
// std:: cout << Root << "\n";
Getans(Root);
int gcd = Gcd(Answer, n * n);
std:: cout << Answer / gcd << "/" << n * n / gcd << "\n";
return ;
}

最新文章

  1. listview控件及其与数据库的连接
  2. python实现的视频下载工具you-get,支持多个国内外主流视频平台
  3. 仿各种APP将文章DOM转JSON并在APP中以列表显示(android、ios、php已开源)
  4. 蒟蒻修养之cf橙名计划2
  5. Android自定义View绘图实现拖影动画
  6. Visaul Studio2015安装以及c++单元测试使用方法
  7. Unity3D实现简单的抽奖程序
  8. Delphi TcxTreelist 表格左边总是缩进去 ,好像有偏移 解决方法
  9. POJ 2395 Out of Hay(最小生成树中的最大长度)
  10. Dapper.SimpleCRUD mysql 插入数据时出现的小插曲
  11. appium+夜神模拟器+python安卓app爬虫初体验
  12. HTTPS建立连接的过程
  13. box-sizing的用法
  14. Java 获取class method parameter name
  15. CentOS 部署 Python3 的一些注意事项
  16. 【Spring】3、BeanFactory 和 ApplicationContext的区别
  17. 开发指南专题十四:JEECG微云高速开发平台MiniDao 介绍
  18. 【oneday_onepage】——Growth Is A Bitch
  19. 133克隆图 &#183; Clone Graph
  20. RDLC报表的相关技巧二(主从报表)

热门文章

  1. JS 06 bom 框窗_页面_定时任务
  2. 在一台服务器上启动多个Broker
  3. gmpy安装使用方法
  4. SpringBoot 第二篇:SpringBoot配置文件使用
  5. rman备份跳过read only数据文件,减少备份总量,加快备份时间
  6. C#利用反射和泛型给不同对象赋值
  7. (二十三)JSP指令
  8. PHP数字转大写
  9. JS OOP -03 JS类的实现
  10. CentOS 系统 MySQL 5.7 开启远程连接