首页 > 代码库 > 【bzoj2152】 聪聪可可

【bzoj2152】 聪聪可可

http://www.lydsy.com/JudgeOnline/problem.php?id=2152 (题目链接)

题意:给出一棵n个节点的带权树,求有多少点对的距离是3的倍数。

solution 
  点分治。对于每个重心统计出每棵子树到重心的距离%3=0/1/2的点的数量即可。求出ans后与n²进行下gcd出解。

代码:

// bzoj2152#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#define MOD 1000000007#define inf 2147483640#define LL long long#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;inline int getint() {    int x=0,f=1;char ch=getchar();    while (ch>‘9‘ || ch<‘0‘) {if (ch==‘-‘) f=-1;ch=getchar();}    while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}const int maxn=20010;struct edge {int  next,to,w;}e[maxn<<2];int head[maxn],d[maxn],t[10],f[maxn],vis[maxn],son[maxn],sum,ans1,ans2,cnt,root,n;void insert(int u,int v,int w) {    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].w=w;    e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;e[cnt].w=w;}void init() {    ans1=cnt=sum=root=0;    scanf("%d",&n);    for (int i=1;i<n;i++) {        int u=getint(),v=getint(),w=getint()%3;        insert(u,v,w);    }    ans2=n*n;}void calroot(int u,int fa) {    son[u]=1;f[u]=0;    for (int i=head[u];i;i=e[i].next) {        if (vis[e[i].to] || e[i].to==fa) continue;        calroot(e[i].to,u);        son[u]+=son[e[i].to];        f[u]=max(f[u],son[e[i].to]);    }    f[u]=max(f[u],sum-son[u]);    if (f[u]<f[root]) root=u;}void caldeep(int u,int fa) {    t[d[u]]++;    for (int i=head[u];i;i=e[i].next) {        if (vis[e[i].to] || e[i].to==fa) continue;        d[e[i].to]=(d[u]+e[i].w)%3;        caldeep(e[i].to,u);    }}int cal(int u,int now) {    t[0]=t[1]=t[2]=0;    d[u]=now;caldeep(u,0);    return t[1]*t[2]*2+t[0]*t[0];}void work(int u) {    ans1+=cal(u,0);    vis[u]=1;    for (int i=head[u];i;i=e[i].next) if (!vis[e[i].to]) {        ans1-=cal(e[i].to,e[i].w);        sum=son[e[i].to];        root=0;        calroot(e[i].to,0);        work(root);    }}int gcd(int a,int b) {    return a%b==0?b:gcd(b,a%b);}int main() {    init();    sum=n;f[0]=inf;    calroot(1,0);    work(root);    int x=gcd(ans1,ans2);    printf("%d/%d",ans1/x,ans2/x);    return 0;}

  

【bzoj2152】 聪聪可可