【题目链接】

https://www.lydsy.com/JudgeOnline/problem.php?id=2152

【算法】

点分治

【代码】

#include<bits/stdc++.h>
using namespace std;
#define MAXN 20010 int i,n,u,v,w,ans1,ans2,g,tot,len,root;
int head[MAXN],size[MAXN],weight[MAXN],d[MAXN],sum[MAXN];
bool visited[MAXN]; struct Edge
{
int to,w,nxt;
} e[MAXN<<]; inline int gcd(int x,int y)
{
if (y == ) return x;
else return gcd(y,x % y);
}
inline void addedge(int u,int v,int w)
{
tot++;
e[tot] = (Edge){v,w,head[u]};
head[u] = tot;
}
inline void getroot(int u,int fa,int total)
{
int i,v;
size[u] = ;
weight[u] = ;
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (v != fa && !visited[v])
{
getroot(v,u,total);
size[u] += size[v];
weight[u] = max(weight[u],size[v]);
}
}
weight[u] = max(weight[u],total - size[u]);
if (weight[u] < weight[root]) root = u;
}
inline void dfs(int u,int fa)
{
int i,v,w;
d[++len] = sum[u];
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (v != fa && !visited[v])
{
sum[v] = (sum[u] + w) % ;
dfs(v,u);
}
}
}
inline int calc(int u)
{
int i;
int ret = ;
int cnt[];
memset(cnt,,sizeof(cnt));
len = ;
dfs(u,);
for (i = ; i <= len; i++) cnt[d[i]]++;
for (i = ; i <= len; i++) ret += cnt[( - d[i]) % ];
return ret;
}
inline void work(int u)
{
int i,v,w;
visited[u] = true;
sum[u] = ;
ans1 += calc(u);
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (!visited[v])
{
sum[v] = w % ;
ans1 -= calc(v);
root = ;
getroot(v,,size[v]);
work(root);
}
}
} int main()
{ scanf("%d",&n);
for (i = ; i < n; i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
memset(visited,false,sizeof(visited));
size[] = weight[] = n;
getroot(,,n);
ans1 = ;
ans2 = n * n;
work(root);
g = gcd(ans1,ans2);
ans1 /= g; ans2 /= g;
printf("%d/%d\n",ans1,ans2); return ;
}

最新文章

  1. InnoDB引擎的索引和存储结构
  2. collections在java中的常见用法
  3. Effective C# 学习笔记(原则二:为你的常量选择readonly而不是const)
  4. activity传递数据
  5. 2875: [Noi2012]随机数生成器 - BZOJ
  6. POJ 1663
  7. 【原创】一起学C++ 之enum ---------C++ primer plus(第6版)
  8. bzoj 1927 [Sdoi2010]星际竞速(最小费用最大流)
  9. SQL Server索引进阶:第六级,标签
  10. 1821: [JSOI2010]Group 部落划分 Group
  11. redis持久化快速回忆手册
  12. spring auto-config
  13. android 控件设置透明度
  14. 是armhf,还是armel?
  15. UML和模式应用3:迭代和进化式分析和设计案例研究
  16. 队列queue 代码
  17. NPM慢怎么办 - nrm切换资源镜像
  18. [转载]FMS Dev Guide学习笔记(验证用户)
  19. pandas 初识(三)
  20. JS+Canvas的棋盘游戏和Java的动态结合

热门文章

  1. 第5章分布式系统模式 在 .NET 中使用 DataSet 实现 Data Transfer Object
  2. MobX入门
  3. Struts2框架学习(三)——配置详解
  4. Walking on the path of Redis --- Redis configuration
  5. HTML5中新增加Input 的种类
  6. RabbitMQ学习之Flow Control
  7. oc懒加载 &amp; swift lazy
  8. ios 编译版本 最低版本 运行版本 动态链接库
  9. apiCloud组件:swiper
  10. 转载:jquery 对 Json 的各种遍历