HDU 4705 Y

Y
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
4
1 2
1 3
1 4

Sample Output
1
Hint
1. The only set is {2,3,4}.

2. Please use #pragma comment(linker, "/STACK:16777216")
 

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;  
}