hdu 4705 dfs统计更新节点信息

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4705

#pragma comment(linker, "/STACK:16777216")
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std; const int maxn = ; long long dp[maxn];
vector<int> G[maxn];
long long num[maxn];
long long N;
long long ans; void dfs(int u,int fa){
for(int i=;i<G[u].size();i++){
int v = G[u][i];
if(v == fa) continue;
dfs(v,u);
num[u] += num[v];
}
long long numfa = N - num[u];
for(int i=;i<G[u].size();i++){
int v = G[u][i];
if(v == fa){
long long temp = num[u]-;
dp[u] += numfa * temp;
continue;
}
long long temp = N - num[v] - ;
dp[u] += num[v] * temp;
}
ans += dp[u];
} int main()
{
// freopen("E:\\acm\\input.txt","r",stdin);
while(cin>>N){
memset(dp,,sizeof(dp));
for(int i=;i<=N;i++) num[i] = ;
for(int i=;i<=N;i++) G[i].clear();
int a,b;
for(int i=;i<=N-;i++){
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
ans = ;
dfs(,-);
long long MAX;
MAX = N*(N-)*(N-); //N写成int,比赛时wa的太痛苦了,还是队友看出来了。以后要注意了。 cout<<(MAX-ans*)/<<endl;
}
return ;
}
上一篇:centos 下使用locate命令


下一篇:C++学习笔记36 (模板的细节明确template specialization)和显式实例(template instantiation)