【题解】9.26模拟赛T2

最新推荐文章于 2022-09-11 15:08:13 发布

丰川样子小孩姐

最新推荐文章于 2022-09-11 15:08:13 发布

阅读量184

点赞数 1

分类专栏：题解树相关文章标签：题解树相关

本文链接：https://blog.csdn.net/ModestCoder_/article/details/101676442

版权

题解同时被 2 个专栏收录

435 篇文章

订阅专栏

树相关

22 篇文章

订阅专栏

本文介绍了一种使用类直径算法寻找最远两点的方法，通过构建图结构并进行深度优先搜索，找到图中距离最远的两个手机店，进而求出这两个点的可行区间求交，以解决特定场景下的选址问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

在这里插入图片描述
用类直径，找出最远的两个手机店，求出这两个手机店的可行区间求交就好了
证明感性/画图皆可
Code：

#include <bits/stdc++.h>
#define maxn 30010
using namespace std;
struct Edge{
	int to, next;
}edge[maxn << 1];
int num, head[maxn], node, Node, Max, n, m, d, a[maxn], b[maxn], flag[maxn], ans;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y){ edge[++num] = (Edge){y, head[x]}, head[x] = num; }

void dfs(int u, int sum, int pre){
	if (sum > Max && flag[u]) Max = sum, node = u;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre) dfs(v, sum + 1, u);
	}
}

void dfs1(int u, int sum, int pre){
	a[u] = 1;
	if (sum == d) return;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre) dfs1(v, sum + 1, u);
	}
}

void dfs2(int u, int sum, int pre){
	b[u] = 1;
	if (sum == d) return;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre) dfs2(v, sum + 1, u);
	}
}

int main(){
	freopen("pb.in", "r", stdin);
	freopen("pb.out", "w", stdout);
	n = read(), m = read(), d = read();
	flag[node = read()] = 1;
	for (int i = 2; i <= m; ++i) flag[read()] = 1;
	for (int i = 1; i < n; ++i){
		int x = read(), y = read();
		addedge(x, y), addedge(y, x);
	}
	Max = -1;
	dfs(node, 0, 0);
	Max = -1, Node = node; 
	dfs(node, 0, 0);
	dfs1(node, 0, 0);
	dfs2(Node, 0, 0);
	for (int i = 1; i <= n; ++i) if (a[i] && b[i]) ++ans;
	printf("%d\n", ans);
	return 0;
}