Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 433    Accepted Submission(s): 147

Problem Description

 

Sample Input

 

Sample Output

 

Source

2013 Multi-University Training Contest 10

 

Recommend

zhuyuanchen520

 

 比赛最后的时候才有的思路，当时有些细节没有想清楚，也没有急着写，赛后写了一下，结果各种错误，除了addeage()函数我没有改过外，其他的几乎都改过，害我查错查到现在。

 有些dp的味道

#include <iostream>

#include <cstring>

#include <queue>

#include <cstdio>

#include <cmath>

#define N 100010

#pragma comment(linker, "/STACK:16777216")

__int64 two[N];

__int64 sum[N];

bool status[N];

int level[N];

struct num

{

    int e,next;

}a[2*N];

int b[N],Top;

int main()

{

    //freopen("data.in","r",stdin);

    void addeage(int x,int y);

    __int64 pre_deal(int k);

    __int64 deal(int k);

    __int64 get_two(int k);

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        Top=0;

        memset(b,-1,sizeof(b));

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

        {

            int x,y;

            scanf("%d %d",&x,&y);

            addeage(x,y);

            addeage(y,x);

        }

        memset(sum,0,sizeof(sum));

        memset(status,false,sizeof(status));

        memset(level,0,sizeof(level));

        pre_deal(1);

        memset(two,0,sizeof(two));

        get_two(1);

        memset(status,false,sizeof(status));

        __int64 res=deal(1);

        printf("%I64d\n",res);

    }

    return 0;

}

void addeage(int x,int y)

{

    a[Top].e = y;

    a[Top].next = b[x];

    b[x]=Top++;

}

__int64 pre_deal(int k)

{

    status[k]=true;

    for(int i=b[k];i!=-1;i=a[i].next)

    {

        int x = a[i].e;

        if(!status[x])

        {

            level[x]=level[k]+1;

            sum[k]+=pre_deal(x);

        }

    }

    sum[k]+=1;

    return sum[k];

}

__int64 get_two(int k)

{

    __int64 s1;

    bool check=true;

    for(int i=b[k];i!=-1;i=a[i].next)

    {

        int y = a[i].e;

        if(level[y]!=level[k]+1)

        {

            continue;

        }

        if(check)

        {

            s1=sum[y];

            check=false;

            continue;

        }

        two[k]+=(s1*sum[y]);

        s1+=sum[y];

    }

    for(int i=b[k];i!=-1;i=a[i].next)

    {

        int y = a[i].e;

        if(level[y]!=level[k]+1)

        {

            continue;

        }

        two[k]+=get_two(y);

    }

    return two[k];

}

__int64 deal(int k)

{

    status[k]=true;

    __int64 s = 0;

    __int64 x2,three=0,s1,temp=0;

    int uv=0;

    bool check=true;

    for(int i=b[k];i!=-1;i=a[i].next)

    {

        int y = a[i].e;

        if(level[y]!=level[k]+1)

        {

            continue;

        }

        if(uv==0)

        {

            s1=sum[y];

            uv++;

            continue;

        }

        if(check)

        {

            temp+=(s1*sum[y]);

            s1+=sum[y];

            check=false;

            continue;

        }

        three+=(temp*sum[y]);

        temp+=(s1*sum[y]);

        s1+=sum[y];

    }

    s+=three;

    __int64 w=0;

    for(int i=b[k];i!=-1;i=a[i].next)

    {

        if(!status[a[i].e])

        {

            s+=deal(a[i].e);

            w+=(sum[a[i].e]);

            s+=two[a[i].e];

        }

    }

    __int64 ans=0;

    for(int i=b[k];i!=-1;i=a[i].next)

    {

        int y =a[i].e;

        __int64 res=0;

        if(level[y]==level[k]+1&&two[y]!=0)

        {

            res+=((w-sum[y])*two[y]);

        }

        ans+=res;

    }

    s+=ans;

    return s;

}