点分板子2333

注释都是错过的地方

 #include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
struct E
{
LL to,nxt,d;
}e[];
LL f1[],ne,sz[];
LL n,sum,root,dep[],ans,fx[];
LL tmp[];
bool vis[];
void getroot(LL u,LL fa)
{
sz[u]=;fx[u]=;
for(LL k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
{
getroot(e[k].to,u);
sz[u]+=sz[e[k].to];
fx[u]=max(fx[u],sz[e[k].to]);
}
fx[u]=max(fx[u],sum-sz[u]);
if(fx[u]<fx[root]) root=u;
}
void getsz(LL u,LL fa)
{
sz[u]=;
for(LL k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
{
getsz(e[k].to,u);
sz[u]+=sz[e[k].to];
}
}
void getdeep(LL u,LL fa)
{
tmp[dep[u]%]++;
for(LL k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
{
dep[e[k].to]=dep[u]+e[k].d;
getdeep(e[k].to,u);
}
}
LL cal(LL u,LL cost)
{
tmp[]=tmp[]=tmp[]=;dep[u]=cost;
getdeep(u,);
return tmp[]*tmp[]+*tmp[]*tmp[];
}
void solve(LL u)
{
ans+=cal(u,);
vis[u]=;//
for(LL k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to])
{
//vis[e[k].to]=1;
getsz(e[k].to,);
sum=sz[e[k].to];//
root=;getroot(e[k].to,);
ans-=cal(e[k].to,e[k].d);//ans-=cal(e[k].to,u);
solve(root);
}
}
int main()
{
LL i,x,y,w;
fx[]=0x3f3f3f3f;
scanf("%lld",&n);
for(i=;i<n;i++)
{
scanf("%lld%lld%lld",&x,&y,&w);
e[++ne].to=y;e[ne].nxt=f1[x];e[ne].d=w;f1[x]=ne;
e[++ne].to=x;e[ne].nxt=f1[y];e[ne].d=w;f1[y]=ne;
}
sum=n;getroot(,);
solve(root);
LL a1=ans,a2=n*n;LL g=__gcd(a1,a2);
a1/=g;a2/=g;
printf("%lld/%lld",a1,a2);
return ;
}

最新文章

  1. js 数组,字符串,json互相转换
  2. VS中批注的使用
  3. 聊聊css hack
  4. usb驱动开发21之驱动生命线
  5. mysql的sql文件的备份与还原
  6. 复制、移动和删除:cp, rm, mv
  7. Linux 高性能server编程——高级I/O函数
  8. Android判断应用程序从后台回到前台
  9. 自行搭建私有云ownCloud,启用SSL,其他配置
  10. Jenkins-Dingding Notification Plugin 配置
  11. Android 的 so 文件加载机制
  12. Expected one result (or null) to be returned by selectOne(), but found: 3
  13. Linux合上笔记本不进入休眠模式
  14. amoeba读写分离
  15. 搜狗输入法在Ubuntu下突然不能输入中文
  16. C++ 中的continue理解
  17. Django signal 信号机制的使用
  18. ASP.NET MVC 学习笔记-4.ASP.NET MVC中Ajax的应用
  19. 线段树基本操作(Segment Tree)
  20. redis集群的远程管理与监控

热门文章

  1. dubbo-admin安装和使用
  2. chapter1:using neural nets to recognize handwritten digits
  3. Linux如何更新软件源
  4. Struts2之struts2标签库了解和使用
  5. 《The Swift Programming Language》的笔记-第28页
  6. 2.NetDh框架之简单高效的日志操作类(附源码和示例代码)
  7. JAVA程序员常用软件整理
  8. apache配置访问限制
  9. ABAP 读取服务器CSV文件到内表
  10. CRM 2011 开发中遇到的问题小结