首页 > ACM题库 > HDU-杭电 > HDU 4705-Y-动态规划-[解题报告]HOJ
2015
09-17

HDU 4705-Y-动态规划-[解题报告]HOJ

Y

问题描述 :

Sum

样例输入:

4
1 2
1 3
1 4

样例输出:

1
Hint
1. The only set is {2,3,4}. 2. Please use #pragma comment(linker, "/STACK:16777216")

1.A,B,C分别位于u的不同儿子

2.A,B分别位于u的不同儿子,C在u的祖先

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;
#pragma comment(linker, "/STACK:16777216")
#define N 100500
#define ll long long
vector<int>vec[N];
int n;
ll ans;
ll s[N],tot[N];
ll dfs(int u,int pre)
{
    for(int i=0;i<vec[u].size();++i)
        if(vec[u][i]!=pre)
    {
        ans+=s[u]*tot[vec[u][i]]*(n-tot[u]);
        ans+=s[u]*tot[vec[u][i]]*(tot[u]-1-s[u]-tot[vec[u][i]]);
        s[u]+=dfs(vec[u][i],u);
    }
    s[u]++;
    return s[u];
}
ll cal(int u,int pre)
{
    for(int i=0;i<vec[u].size();++i)
        if(vec[u][i]!=pre)
        tot[u]+=cal(vec[u][i],u);
    tot[u]++;
    return tot[u];
}
int main ()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;++i)
            vec[i].clear();
        ans=0;
        memset(s,0,sizeof(s));
        memset(tot,0,sizeof(tot));
        for(int i=1,u,v;i<n;++i)
        {
            scanf("%d%d",&u,&v);
            vec[u].push_back(v);
            vec[v].push_back(u);
        }
        cal(1,-1);
        dfs(1,-1);
        cout<<ans<<endl;
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/jackyguo1992/article/details/10972639