bzoj2152 树分治

还是太菜了,自己写的wa,但是找不到哪里错了,,

感觉现在学树分治早了点。。以后回来再看吧

/*
多少点对之间的路径是3的倍数
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#include<algorithm>
#define MAXN 20010
int N;
struct E{
int v,next,w;
}edge[MAXN<<];
int head[MAXN],tot;
int size[MAXN];
int maxv[MAXN];
int vis[MAXN];
int dis[MAXN];
int num,ans,Max,root;
void init(){
tot=ans=;
memset(head,-,sizeof head);
memset(vis,,sizeof vis);
}
void addedge(int u,int v,int w){
edge[tot].v=v;
edge[tot].w=w;
edge[tot].next=head[u];
head[u]=tot++;
}
//一次dfs处理子树的大小
void dfssize(int u,int f){
size[u]=;
maxv[u]=;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].v;
if(v==f||vis[v]) continue;
dfssize(v,u);
size[u]+=size[v];
maxv[u]=max(maxv[u],size[v]);
}
}
//一次dfs找重心
void dfsroot(int r,int u,int f){
maxv[u]=max(maxv[u],size[r]-maxv[u]);
if(maxv[u]<Max)
Max=maxv[u],root=u;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].v;
if(v==f||vis[v])
continue;
dfsroot(r,v,u);
}
}
int tmp[];
//一次dfs求路径长度
void dfsdis(int u,int d,int f){
dis[u]=d%;
tmp[dis[u]]++;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].v;
if(v==f||vis[v])
continue;
dfsdis(v,d+edge[i].w,u);
}
}
//计算以u为根的子树中有多少点对的距离%3==0
int calc(int u,int d){
tmp[]=tmp[]=tmp[]=;
dfsdis(u,d,-);//得到dis数组
return tmp[]*tmp[]+tmp[]*tmp[]*;
}
//分治
void dfs(int u){
Max=N;
dfssize(u,-);
dfsroot(u,u,-);
ans+=calc(root,);
vis[root]=;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].v;
if(vis[v])
continue;
ans-=calc(v,edge[i].w);
dfs(v);
}
} int gcd(int a,int b){
if(b==) return a;
else return gcd(b,a%b);
}
int main(){
scanf("%d",&N);
init();
for(int i=;i<=N-;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w%);
addedge(v,u,w%);
}
dfs();
int g=gcd(ans,N*N);
printf("%d/%d",ans/g,N*N/g);
return ;
}
上一篇:贪心算法-找零钱(C#实现)


下一篇:Spring框架针对dao层的jdbcTemplate操作crud之delete删除数据库操作 Spring相关Jar包下载