bzoj 2152: 聪聪可可

 #include<cstdio>
#include<algorithm>
using namespace std;
const int N=;
int t[],head[N],son[N],f[N],d[N],root,ans,n,sum,cnt;
bool vis[N];
struct ee{int to,next,v;}e[N*];
void insert(int u,int v,int w){
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;
} int gcd(int a1,int a2)
{
int a3=a1%a2;
for(;a3;)
{
a1=a2;
a2=a3;
a3=a1%a2;
}
return a2;
} void getroot(int x,int fa){
son[x]=;f[x]=;
for (int i=head[x];i;i=e[i].next){
int v=e[i].to;
if (!vis[v]&&v!=fa){
getroot(v,x);
son[x]+=son[v];
f[x]=max(f[x],son[v]);
}
}
f[x]=max(f[x],sum-son[x]);
if (f[root]>f[x])root=x;
} void getdeep(int x,int fa){
t[d[x]]++;
for (int i=head[x];i;i=e[i].next){
int v=e[i].to;
if (v!=fa&&!vis[v]){
d[v]=(d[x]+e[i].v)%;
getdeep(v,x);
}
}
} int cal(int x,int now){
t[]=t[]=t[]=;
d[x]=now;
getdeep(x,);
return t[]*t[]*+t[]*t[];
} void work(int x){
ans+=cal(x,);
vis[x]=;
for (int i=head[x];i;i=e[i].next){
int v=e[i].to;
if (!vis[v]) {
ans-=cal(v,e[i].v);
root=;sum=son[v];
getroot(v,);
work(root);
}
}
} int main(){
scanf("%d",&n);
int u,v,w;
for (int i=;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
w%=;
insert(u,v,w);
insert(v,u,w);
}
f[]=sum=n;
root=;
getroot(,);
work(root);
int t=gcd(ans,n*n);
printf("%d/%d",ans/t,n*n/t);
}

树的点分治  首先找树的重心,把根节点设为树的重心。然后进行点分治(就是从根开始,看经过根的方案数,在把根删掉,求每棵子树)。

上一篇:C#中this的用法,你用过几种?


下一篇:Android 安装镜像