Codeforces 1294F Three Paths on a Tree

题目链接:

Codeforces 1294F Three Paths on a Tree

思路:

首先三个点中有两个点一定是该树的直径之一的两个端点,我们设为a,b;(不会证明orz)
还剩一个点c,设len(a,b)len(a,b)len(a,b)是a到b的距离,则答案即为len(a,b)+len(b,c)+len(a,c)2\frac{len(a,b)+len(b,c)+len(a,c)}{2}2len(a,b)+len(b,c)+len(a,c)​;
因为len(a,b)len(a,b)len(a,b)已经确定是树的直径长度,至于点c,我们遍历所有不是a、b的点,求得最大的len(a,c)+len(b,c)len(a,c)+len(b,c)len(a,c)+len(b,c)即可;

代码:

#include<bits/stdc++.h>

using namespace std;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

const int maxn = 2e5 + 5;
vector<int> G[maxn];
int vst[maxn], sum[maxn];
int bfs(int u) {
	memset(vst, 0, sizeof(vst));
	queue<int> que;
	que.push(u);
	int now;
	while(!que.empty()) {
		now = que.front();
		que.pop();
		for(int & x : G[now]) if(!vst[x] && x != u) {
			que.push(x);
			vst[x] = vst[now] + 1;
		}
	}
	return now;
}

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	int n = read();
	for(int i = 1; i < n; i++) {
		int a = read(), b = read();
		G[a].push_back(b);
		G[b].push_back(a);	
	}
	int x = bfs(1), y = bfs(x), ans = 0, best;
	for(int i = 1; i <= n; i++) sum[i] += vst[y] + vst[i];
	bfs(y);
	for(int i = 1; i <= n; i++) {
		sum[i] += vst[i];
		if(i != x && i != y && sum[i] > ans) ans = sum[i], best = i;
	}
	printf("%d\n%d %d %d", ans / 2, x, y, best);
	return 0;
}
Codeforces 1294F Three Paths on a TreeCodeforces 1294F Three Paths on a Tree Yuhan の Blog 发布了300 篇原创文章 · 获赞 8 · 访问量 7524 私信 关注
上一篇:前端跨域配置


下一篇:原题链接在这里:980. Unique Paths III