BZOJ3522 [Poi2014] Hotel 【DFS】

tonyfang posted @ 2016年9月04日 21:11 in BZOJ with tags C++ OI , 189 阅读

题目大意:有$n$个点,问有多少个三点组,满足组内每两个的点的距离相等。$n \leq 5000$。

【题解】

考虑两种情况:链和非链。如果三点成链,不可能构成。如果不共链,一定有一个中心点,三个点分在这个点为根的不同子树中,那么枚举中心点DFS计数即可。

 

# include <stdio.h>
# include <string.h>
using namespace std;

int n;
int head[5050], next[100010], to[100010], tot=0;
int depth[5050];
typedef long long ll;
ll ans=0, f[5050], g[5050];

inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

inline void dfs(int x, int fa, int dep) {
	depth[dep] ++;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa) continue;
		dfs(to[i], x, dep+1);
	}
}

int main() {
	scanf("%d", &n);
	for (int i=1, u, v; i<n; ++i) {
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	for (int pnt=1; pnt<=n; ++pnt) {
		memset(f, 0, sizeof(f));
		memset(g, 0, sizeof(g));
		for (int j=head[pnt]; j; j=next[j]) {
			memset(depth, 0, sizeof(depth));
			dfs(to[j], pnt, 1);
			for (int k=1; k<=n; ++k) {
				ans = ans + (ll)g[k]*depth[k];
				g[k] = g[k] + f[k]*depth[k];
				f[k] += depth[k];
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter