做的第二道点分治的题目,比较裸,算是模板题吧(感觉比之前那题还简单点。

题目:BZOJ 2152 聪聪可可

题目大意:给出一棵树,求树上两点间长度为3的倍数(0也算)的路径数。

解题思路:

基本和POJ1741一样

2.不过重心,在重心的子树中

情况二可通过分治转化为情况1。

通过dfs求出每个点到重心的距离%3,将余数是1的和是2的配对,余数是0的两两配对,得出路径数。

同样的,注意去重。

代码:

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; struct edge{
int w,to,next;
}e[]; int head[],s[],f[],d[],t[],ans,size;
bool b[];
int n,i,j,v,w,x,y,ne=,root; void add(int a,int b,int c){
e[++ne].to=b; e[ne].w=c; e[ne].next=head[a]; head[a]=ne;
} void getroot(int k,int fa){
int v,i;
s[k]=;f[k]=;
for(i=head[k];i!=-;i=e[i].next){
v=e[i].to;
if(v!=fa&&!b[v]){
getroot(v,k);
s[k]+=s[v];
f[k]=max(f[k],s[v]);
}
}
f[k]=max(f[k],size-s[k]);
if(f[k]<f[root])root=k;
} void getdis(int k,int fa){
int v,i;
t[d[k]]++;//将对应余数的数目+1;
for(i=head[k];i!=-;i=e[i].next){
v=e[i].to;
if (v!=fa&&!b[v]){
d[v]=(d[k]+e[i].w)%;
getdis(v,k);
}
}
} int clac(int k,int init){
t[]=t[]=t[]=;//余数清0
d[k]=init%;
getdis(k,);//计算深度
return (t[]*t[]*+t[]*t[]);//计算路径数
} void work(int k){
int i,v;
ans+=clac(k,);//更新ans
b[k]=true;
for(i=head[k];i!=-;i=e[i].next){
v=e[i].to;
if(!b[v]){
ans-=clac(v,e[i].w);//去重
f[]=size=s[v];
root=;
getroot(v,);//更新重心
work(root);//求解子树
}
}
} int gcd(int a,int b){
if(b==) return a;
return gcd(b,a%b);
} int main(){
ans=root=;
memset(head,-,sizeof(head));
memset(b,,sizeof(b));
scanf("%d",&n);
for(i=;i<n;i++){
scanf("%d%d%d",&x,&y,&w);
w%=;
add(x,y,w);
add(y,x,w);//连双向边
}
f[]=size=n;
getroot(,);//求重心
work(root);
int tmp=gcd(ans,n*n);
printf("%d/%d\n",ans/tmp,n*n/tmp);
}

最新文章

  1. [测]jieba分词
  2. JS数字键盘
  3. Configure Amazon RDS mysql to store Chinese Characters
  4. TabBarController
  5. PowerShell监控Windows打印服务器
  6. 08---Net基础加强
  7. Linux的内存回收和交换
  8. 下一个系列学习列表Spring.net+NHibernate+MVC
  9. AndroidManifest.xml解释说明和android的启动过程
  10. PHP设计模式笔记四:适配器模式 -- Rango韩老师 http://www.imooc.com/learn/236
  11. SpringMVC+GSON 对象序列化--日期格式的处理
  12. 【转】解决未能加载文件或程序集&#39;WebGrease‘的问题
  13. 知识点---&lt;input&gt;、&lt;textarea&gt;
  14. WCF 的学习过程
  15. ASPxGridView 用法
  16. C# 实体/集合差异比较,比较两个实体或集合值是否一样,将实体2的值动态赋值给实体1(名称一样的属性进行赋值)
  17. IT部门不应该是一个后勤部门
  18. tomcat7部署多个web应用不同编码,端口
  19. Java实现日历小程序【代码】
  20. URL query string中文字符问题

热门文章

  1. pywin32获得tkinter的Canvas窗口句柄,并在上面绘图
  2. 动态类型识别&amp;动态创建
  3. OpenMP笔记(六)
  4. neo4jcypher基本语句
  5. main函数的参数(int argc,char *argv[])
  6. 干货 | 玩转云文件存储——利用CFS实现web应用的共享访问
  7. Facebook的Libra “区块链”到底是如何运作的?
  8. Python7DAY-基础语法.md
  9. let和var的区别
  10. restful的简单使用