点分治裸题,甚至不需要栈回撤。

尝试用容斥写了一波,就是把所有子树混一块计算,最后减去子树内路径条数。

#include<iostream>
#include<cstring>
#include<cstdio> using namespace std; inline int rd(){
int ret=,f=;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-:;
while(isdigit(c))ret=ret*+c-'',c=getchar();
return ret*f;
} const int MAXN=; struct Edge{
int next,to,w;
}e[MAXN<<];
int ecnt,head[MAXN];
inline void add(int x,int y,int w){
e[++ecnt].next = head[x];
e[ecnt].to = y;
e[ecnt].w = w;
head[x] = ecnt;
} int n,m;
bool vis[MAXN];
int siz[MAXN];
void getsiz(int x,int pre){
siz[x]=;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(vis[v]||v==pre) continue;
getsiz(v,x);
siz[x]+=siz[v];
}
}
int root,mn;
void getroot(int x,int pre,int tot){
int mx=;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(vis[v]||v==pre) continue;
mx=max(mx,siz[v]);
getroot(v,x,tot);
}
mx=max(mx,tot-siz[x]);
if(mx<mn) mn=mx,root=x;
}
int f[];
int s[MAXN]; void dfs(int x,int pre,int dis){
s[++s[]]=dis%;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(vis[v]||v==pre) continue;
dfs(v,x,(dis+e[i].w)%);
}
} long long ans=; void dac(int x){
mn=n;f[]=;
getsiz(x,-);
getroot(x,-,siz[x]);
int u=root;vis[u]=;
int offset=;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(vis[v]) continue;
s[]=;dfs(v,u,e[i].w%);
int t0=,t1=,t2=;
for(int j=s[];j>=;j--){
if(s[j]==) t0++;
if(s[j]==) t1++;
if(s[j]==) t2++;
}
offset+=t0*t0+*t1*t2;
for(int j=s[];j>=;j--){
f[s[j]]++;
}
}
ans+=f[]*f[]+*f[]*f[]-offset;
memset(f,,sizeof(f));
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(!vis[v]) dac(v);
}
} long long gcd(long long x,long long y){
return !y?x:gcd(y,x%y);
} int main(){
n=rd();
int x,y,w;
for(int i=;i<=n-;i++){
x=rd();y=rd();w=rd();
add(x,y,w%);add(y,x,w%);
}
dac();
long long tmp=1ll*n*n;
long long G=gcd(tmp,ans);
printf("%lld/%lld",ans/G,tmp/G);
return ;
}

最新文章

  1. GJM : Unity3D - NetWork - Hight Level API ( HLAPI) [转载]
  2. [Weblogic]如何清理缓存
  3. input:focus
  4. 程序员书单_UML篇
  5. 使用JMeter创建FTP测试计划
  6. 淘宝Refrash_token签名错误的解决办法
  7. 【模拟】HDU 5774 Where Amazing Happens
  8. Ubuntu14.04 weblogic11g集群环境测试
  9. 【翻译】Sencha Ext JS 5公布
  10. 10个带源码的充满活力的Web设计教程
  11. leetcode-004 insertion sort list
  12. Java设置Excel有效性
  13. ZooKeeper入门搭建教程
  14. HTML空格符号 nbsp; ensp; emsp; 介绍以及实现中文对齐的方法
  15. (转)Visual Studio控制台程序输出窗口一闪而过的解决方法
  16. mysql数据库基于LVM快照的备份
  17. RMAN-05541: no archived logs found in target database
  18. java中垃圾回收机制中的引用计数法和可达性分析法(最详细)
  19. Nginx 基础知识学习
  20. java语言登陆界面(菜鸟版)

热门文章

  1. Java基础笔记(二)——配置环境变量
  2. C# 数组之List&lt;T&gt;
  3. Codeforces 161D(树形dp)
  4. 2017浙江工业大学-校赛决赛 XiaoWei的战斗力
  5. NET?.NET Framework?.NET Core?
  6. ExceptionHandlerMiddleware中间件如何呈现“定制化错误页面”
  7. (转)CentOS之7与6的区别
  8. 下一代的前端构建工具:parcel打包react
  9. webpack.config.js====插件purifycss-webpack,提炼css文件
  10. 集合(Map、可变参数、Collections)