BZOJ2152 聪聪可可

2014.12.10 16:26 Wed| 2 visits oi_2015| 2015_刷题日常| Text

这是我写过的第一道树分治么?哦,这是我第一次知道我写的是树分治。

Solution

其实解法还是蛮暴力的。找重心,计算经过这个重心的符合题意的路径条数,这一过程可以再用一个DFS。由于这样会加重,所以在递归子树的时候还要减去多加的部分。具体见代码。

//一大堆DFS什么的真是够了!!!

//还有这一次数组怎么又开小了!!!手残毁一生啊!!!

PS:其实这道题根本不需要点分治,一个树形DP就解决问题了。BZOJ,你的提示又在逗我……

Code

#include <bits/stdc++.h>
using namespace std;
#define N 20005
#define inf 0x3f3f3f3f

int head[N],next[N*2],to[N*2],val[N*2],cnt;
int t,n,size[N],maxs[N],vis[N],root,ans;

inline void add(int x,int y,int z)
{
    to[++cnt]=y; val[cnt]=z;
    next[cnt]=head[x]; head[x]=cnt;
}

void findroot(int sum,int x,int fa)
{
    size[x]=1; maxs[x]=0;
    for(int y,i=head[x];i;i=next[i])
        if((y=to[i])!=fa&&!vis[y])
            findroot(sum,y,x),
            size[x]+=size[y],
            maxs[x]=max(maxs[x],size[y]);
    maxs[x]=max(maxs[x],sum-size[x]);
    if(maxs[x]<maxs[root]) root=x;
}

void getcnt(int t[],int x,int fa,int d)
{
    t[d]++;
    for(int i=head[x],y;i;i=next[i])
        if((y=to[i])!=fa&&!vis[y])
            getcnt(t,y,x,(d+val[i])%3);
}

int addans(int x,int d)
{
    int t[3]={0};
    getcnt(t,x,0,d);
    return t[0]*t[0]+t[1]*t[2]*2;
}

void getans(int x)
{
    ans+=addans(x,0);
    vis[x]=1;
    for(int y,i=head[x];i;i=next[i])
        if(!vis[y=to[i]])
        {
            ans-=addans(y,val[i]);
            root=0;
            findroot(size[y],y,0);
            getans(root);
        }
}

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{
    cin>>n;
    for(int i=1,x,y,z;i<n;i++)
        x=read(),y=read(),z=read()%3,
        add(x,y,z), add(y,x,z);
    maxs[0]=inf;
    findroot(n,1,0);
    getans(root);
    int gcd=__gcd(ans,n*n);
    cout<<ans/gcd<<'/'<<n*n/gcd<<endl;
}