题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2152

思路:

要想两点之间距离为3的倍数,那么用t0表示该点距离重心的距离对3取模为0,依此得t1,t2,那么两点之间距离为3的倍数只有三种可能:t1-t2,t2-t1,t0-t0,将所有和重心的具体全部统计好,最后t1*t2*2+t0*t0就是

为3的倍数的点对数量

实现代码:

#include<bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff
const int M = 1e5+;
int siz[M],f[M],head[M],vis[M],ans,cnt,t[M],sum,root,d[M];
struct node{
int to,next,w;
}e[M<<]; void init(){
ans = ;
cnt = ;
memset(vis,,sizeof(vis));
memset(head,,sizeof(head));
} void add(int u,int v,int w){
e[++cnt].to = v; e[cnt].w = w; e[cnt].next = head[u]; head[u] = cnt;
} void get_root(int u,int fa){
siz[u] = ; f[u] = ;
for(int i = head[u];i;i = e[i].next){
int v = e[i].to;
if(v != fa&&!vis[v]){
get_root(v,u);
siz[u] += siz[v];
f[u] = max(f[u],siz[v]);
}
}
f[u] = max(f[u],sum - siz[u]);
if(f[u] < f[root]) root = u;
return ;
} void get_dis(int u,int fa){
t[d[u]]++;
for(int i = head[u];i;i = e[i].next){
int v = e[i].to;
if(v != fa&& !vis[v]){
d[v] = (d[u] + e[i].w)%;
get_dis(v,u);
}
}
return ;
} int cal(int u,int c){
t[] = t[] = t[] = ;
d[u] = c;
get_dis(u,);
return t[]*t[]*+t[]*t[];
} void solve(int v){
ans += cal(v,); vis[v] = ;
for(int i = head[v];i;i = e[i].next){
int v = e[i].to;
if(!vis[v]){
ans -= cal(v,e[i].w);
sum = siz[v];
root = ;
get_root(v,);
solve(root);
}
}
} int main()
{
ios::sync_with_stdio();
cin.tie(); cout.tie();
int m,u,v,w,n;
cin>>n;
init();
for(int i = ;i <= n-;i ++){
cin>>u>>v>>w;
w%=;
add(u,v,w);
add(v,u,w);
}
f[] = inf;
sum = n;
root = ;
get_root(,);
solve(root);
int x = __gcd(ans,n*n);
cout<<ans/x<<"/"<<n*n/x<<endl;
return ;
}

最新文章

  1. CentOS7清理yum缓存和释放内存方法
  2. oracle远程连接配置
  3. iOS常用公共方法
  4. 利用should.js进行测试
  5. 利用Python的三元表达式解决Odoo中工资条中城镇、农村保险的问题
  6. 【Unity Shaders】学习笔记——SurfaceShader(九)Cubemap
  7. maven整合s2sh截图
  8. ACE的 日志
  9. 让hyper-v虚拟机中类ubuntu系统可以全屏
  10. 【转】Optiplex 7010驱动下载链接(XP&amp;Windows7
  11. java--对象比较器
  12. 项目中dubbo的使用
  13. hibernate异常:org.hibernate.NonUniqueObjectException
  14. 多个dropdownlist只有第一个能选中,其他选不中之我见
  15. RasterBandClass Class
  16. C++入门篇十三
  17. Exp1 PC平台逆向破解 20165110 石钰
  18. String、StringBuffer和StringBulder
  19. Codeforces Round #425 (Div. 2) Problem A Sasha and Sticks (Codeforces 832A)
  20. layer插件学习——弹框(自定义页)

热门文章

  1. HDU 4857 逃生(反向建边的拓扑排序+贪心思想)
  2. pip安装python包出错:Could not find a version that satisfies the requirement skimage (from versions: )
  3. Nginx 服务器的安装部署(CentOS系统)
  4. 线程池原理及python实现
  5. Spring + SpringMVC配置
  6. 20155216 实验一 逆向与Bof基础
  7. POJ1807&amp;&amp;1276
  8. 如何在web api中使用SignalR
  9. NX 栈不可执行的绕过方式--ROP链
  10. FFMPEG的基础使用