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

题意就是给一棵树，然后问不在一条链上的三个点有多少种。

树形DP，直接求不好求，先求其补集。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#pragma comment(linker, "/STACK:16777216")
const int maxn = 100100;

vector<int> son[maxn];
int f[maxn], x, y;
long long n, ans;

void clear() {
	for (int i = 0; i < maxn; i++)
		son[i].clear();
	memset(f, 0, sizeof(f));
	ans = 0;
}

void dfs(int u, int fa) {
	long long tmp = 0;
	f[u] = 1;
	for (int i = 0; i < son[u].size(); i++) {
		int v = son[u][i];
		if (v == fa)
			continue;
		dfs(v, u);
		f[u] += f[v];
		ans += tmp * f[v];
		tmp += f[v];
	}
	ans += tmp * (n - f[u]);
}

void init() {
	clear();
	for (int i = 1; i < n; i++) {
		cin >> x >> y;
		son[x].push_back(y);
		son[y].push_back(x);
	}
}

void work() {
	dfs(1, -1);
	long long res = n * (n-1) * (n-2) / 6;
	cout << res - ans << endl;
}

int main() {
	while (cin >> n) {
		init();
		work();
	}
	return 0;
}