bzoj2152: 聪聪可可树分治

sb树分治
/**************************************************************

    Problem: 2152

    User: walfy

    Language: C++

    Result: Accepted

    Time:472 ms

    Memory:3720 kb

****************************************************************/

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double eps=1e-6;

const int N=20000+10,maxn=5000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

struct edge{

    int to,Next,c;

}e[N*4];

int cnt,head[N],num[10];

void init()

{

    cnt=0;

    memset(head,-1,sizeof head);

}

void add(int u,int v,int c)

{

    e[cnt].to=v;

    e[cnt].c=c;

    e[cnt].Next=head[u];

    head[u]=cnt++;

}

int vis[N],sz[N],zx[N];

void dfssz(int u,int f)

{

    sz[u]=1;

    for(int i=head[u];~i;i=e[i].Next)

    {

        int x=e[i].to;

        if(x==f||vis[x])continue;

        dfssz(x,u);

        sz[u]+=sz[x];

    }

}

void dfszx(int u,int f,int o,int &ans)

{

    zx[u]=sz[o]-sz[u];

    for(int i=head[u];~i;i=e[i].Next)

    {

        int x=e[i].to;

        if(x==f||vis[x])continue;

        zx[u]=max(zx[u],sz[x]);

        dfszx(x,u,o,ans);

    }

    if(ans==-1||zx[ans]>zx[u])ans=u;

}

int findzx(int u,int f)

{

    dfssz(u,f);

    int ans=-1;

    dfszx(u,f,u,ans);

    return ans;

}

void dfsroot(int u,int f,int sum)

{

    num[sum%3]++;

    for(int i=head[u];~i;i=e[i].Next)

    {

        int x=e[i].to;

        if(x==f||vis[x])continue;

        dfsroot(x,u,sum+e[i].c);

    }

}

int cal()

{

    return num[0]*(num[0]-1)/2+num[1]*num[2];

}

int solve(int o,int f)

{

    int root=findzx(o,f);

    memset(num,0,sizeof num);

    dfsroot(root,-1,0);

//    printf("++++%d %d %d %d\n",num[0],num[1],num[2],cal());

    int ans=cal();

    vis[root]=1;

    for(int i=head[root];~i;i=e[i].Next)

    {

        int x=e[i].to;

        if(x==f||vis[x])continue;

        memset(num,0,sizeof num);

        dfsroot(x,root,e[i].c);

//        printf("----%d %d %d %d\n",num[0],num[1],num[2],cal());

        ans-=cal();

    }

    for(int i=head[root];~i;i=e[i].Next)

    {

        int x=e[i].to;

        if(x==f||vis[x])continue;

        ans+=solve(x,root);

    }

    return ans;

}

int main()

{

    int n;

    scanf("%d",&n);

    init();

    for(int i=1;i<n;i++)

    {

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c);

        add(a,b,c);add(b,a,c);

    }

    int ans1=solve(1,-1)*2+n;

    int ans2=n*n;

    int p=__gcd(ans1,ans2);

    printf("%d/%d\n",ans1/p,ans2/p);

    return 0;

}

/********************

********************/
巴特西

bzoj2152: 聪聪可可树分治

最新文章

热门文章

巴特西

bzoj2152: 聪聪可可 树分治

最新文章

热门文章

bzoj2152: 聪聪可可树分治
