题意
给定一棵树，计算数集｛A,B,C｝的个数，其中A,B,C是树上的节点，且不存在一条路径覆盖A,B,C。
思路
朴素的想法是枚举“Y”的中点，然后枚举三条树枝i,j,k，答案就是sigma(Si*Sj*Sk) = [( sigma(Si) )^3 - 3*sigma(Si)*sigma(Si^2) + 2*sigma(Si^3)] / 6，其中Si表示i子树上节点个数。但是这样太麻烦了。
我们考虑用
补集来做。计算A,B,C被一条路径覆盖的个数。那么这样假设A<B<C，我们就可以枚举B，然后枚举两个树枝i,j，答案就是sigma(Si*Sj) =[ ( sigma(Si) )^2 - sigma ( Si^2 ) ] / 2，时间复杂度O(n)。
代码
[cpp]
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#define MID(x,y) ((x+y)/2)
#define MEM(a,b) memset(a,b,sizeof(a))
#define REP(i, begin, end) for (int i = begin; i <= end; i ++)
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long LL;
typedef vector <int> VI;
const int MAXV = 100005;
int n;
VI adj[MAXV];
LL res, num[MAXV];
bool vis[MAXV];
void dfs(int u){
vis[u] = true;
int son = 0;
num[u] = 1;
VI tmpadj;
for (int i = 0; i < (int)adj[u].size(); ++ i){
int v = adj[u][i];
if (!vis[v]){
tmpadj.push_back(v);
son ++;
dfs(v);
num[u] += num[v];
}
}
if (son > 0){
if (u == 1 && son == 1) return ;
LL uans = (LL)(n-1)*(n-1);
for (int i = 0; i < (int)tmpadj.size(); ++ i){
int v = tmpadj[i];
uans -= (LL)num[v] * num[v];
}
uans -= (LL)(n-num[u])*(n-num[u]);
uans /= 2;
res += uans;
}
return ;
}
int main(){
while(scanf("%d", &n) != EOF){
REP(i, 0, n) adj[i].clear();
REP(i, 1, n-1){
int u, v;
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
res = 0;
MEM(num, 0);
MEM(vis, false);
dfs(1);
printf("%I64d
", (LL)n*(n-1)*(n-2)/6 - res);
}
return 0;
}
[/cpp]
