BZOJ3522 [Poi2014] Hotel 【DFS】

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

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




# 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) {

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;
BSNL Internet settin 说:
2023年2月07日 15:41

Find the new different Access Network Points to configure for different organizations to access 2G / 3G / 4G high speed BSNL mobile internet, where Today every mobile customer subscribes with unlimited 4G internet plans to access internet on their 3G, 4G smart mobiles or wireless phones, BSNL Internet settings and for the best high speed connectivity, a gateway is required i.e. nothing but BSNL APN Settings or simply BSNL APN. 说:
2023年4月20日 01:01

Board Sample Paper 2023 Aspirants who had Registered for the Board Exam can Download the Previous Paper When Board Announces the Dates to Download the Sample Paper. Board Sample Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Provided Details for More Information About the Board Sample Paper.

登录 *

loading captcha image...
or Ctrl+Enter