BZOJ3522 [Poi2014] Hotel 【DFS】

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

题目大意:有$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;
}
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.

samplepaper.in 说:
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. samplepaper.in 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