Y
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 60 Accepted Submission(s): 20
Problem Description
Sample Input
4
1 2
1 3
1 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
Recommend
zhuyuanchen520
树形DP统计一遍就可以了。
/* ***********************************************
Author :kuangbin
Created Time :2013/8/22 12:27:59
File Name :F:\2013ACM练习\2013多校10\1010.cpp
************************************************ */
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std; const int MAXN = ;
struct Edge
{
int to,next;
}edge[MAXN*];
int head[MAXN],tot;
void init()
{
memset(head,-,sizeof(head));
tot = ;
}
void addedge(int u,int v)
{
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
} int num[MAXN];
int n;
long long ans;
void dfs(int u,int pre)
{
num[u] = ;
int tmp = ;
for(int i = head[u];i!= -;i = edge[i].next)
{
int v = edge[i].to;
if(v == pre)continue;
dfs(v,u);
ans += (long long)tmp*num[v];
num[u] += num[v];
tmp += num[v];
}
ans += (long long)tmp*(n-num[u]);
} int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int u,v;
while(scanf("%d",&n) == )
{
init();
for(int i = ;i < n;i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
ans = ;
dfs(,-);
long long tot = (long long)n*(n-)*(n-)/;
printf("%I64d\n",tot-ans);
}
return ;
}