Codeforces Round #615 (Div. 3) F 运行最快的做法！！
一开始输出是cout，发现就第二了，改printf就直接第一快了。我说下这题我的做法是什么。题目就是给你一棵树，叫你给出三个点，这三个点相连的简单路径的边数最多。样例的图解释的很清楚是什么意思了。
怎么做呢？我一开始首先考虑两个点相连的情况，两个点的情况下什么时候会是拥有最长的边数？很明显就是大家都知道的两个点是树直径的端点时候，树直径大家都会，随便找一点bfs/dfs出最远的一个点，这个点就是树直径的其中一个端点，然后普通树直径的另一个端点就是从这个已知端点出发，再跑一次，跑出第二个端点。
两个点就确定了，接下来我们要考虑要怎么得出第三个点？由于我们是跑出来了树直径，在直径上的每个点（除了端点）,都是会在延伸出其他的枝叶（连着其他的边，但是这个边不在直径里面），很明显我们要的第三个点，就是在树直径上的点延伸出去的最远的那个点去作为第三个点。
这个例子的绿线就是树直径，黄色的点就是题目要求的三个点。
那么如何跑出这个第三个点呢？理论上，我们去得到树的直径上有哪些点/边，去dfs跑另外的边，这样是可行的。
但是我的做法就是与求第二个点的坐标一起跑出来。
我们思考下，当我们求出树直径的第一个点point1的时候，是不是就是可以当做以这个点为根的树，那么树直径另一个端点在哪里呢？在以point1为根的树的深度最深的任意一个点。只要我们求出深度最深的点，也就是知道point2，树直径的第二个点，然后我们在这遍求深度的dfs中，可以维护一些其他东西让我们能得出第三个点
- father[i], 记录的是i点的父亲是谁
- maxdep[i],以i为根的子树中， 深度最远的节点的深度是多少
- maxdeppoint[i] 以i为根的子树中，深度最远的节点是谁？
- deep_[i] , 节点i的深度
很明显2,3我们只要在dfs的时候去判断一下就好了，这就类似dp？
for (int i = head[now]; i; i = xian[i].next) {
int to = xian[i].to;
if (to == fa)continue;
dfs(to, now);
if (maxdep[now] < maxdep[to]) {
maxdep[now] = max(maxdep[now], maxdep[to]);
maxdeppoint[now] = maxdeppoint[to];
}
}
接下来解释下怎么跑出第三个点，首先我们根据深度就可以知道point2，就是树直径另一个端点。然后我们根据father【i】就可以吧树直径上所有点都标记上，写个while。
然后我们去遍历所有点，只要这个点不是在树直径上，并且这个点的父亲是在树直径上，（为什么点的父亲需要在直径上？因为如果点的父亲不在直径上，那么这个点的父亲所能提供的贡献肯定比当前点大）那么就去算出这条枝干能提供的贡献（该点位根的最远深度减去父亲的深度），找出最大贡献的枝干，根据我们的maxdeppoint就可知道第三个点的下标。
下面是代码（46ms）
#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<time.h>
#include<string>
#include<cmath>
#include <ctime>
#include<bitset>
#include <cctype>
#define low_bit(x) ((x)&(-(x)))
#define debug cout<<"*********degug**********";
#define index index_
#define ll long long
#define RE register
#define yn yn_
using namespace std;
const long long max_ = 3e5 + 7;
const int mod = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e18;
int read() {
int s = 0, f = 1;
char ch = getchar();
while (ch<'0' || ch>'9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0'&&ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
inline int min(int a, int b) {
return a < b ? a : b;
}
inline int max(int a, int b) {
return a > b ? a : b;
}
int head[max_], xiann = 2,father[max_],deep_[max_],n,vis[max_],point1,maxdep[max_],md = 0, point2,aim[max_], point3, maxdeppoint[max_];
struct {
int next, to;
}xian[max_ * 2];
inline void add(int a, int b) {
xian[xiann].next = head[a];
xian[xiann].to = b;
head[a] = xiann;
xiann++;
}
queue<int>que;
void bfs() {
que.push(1);
while (!que.empty()){
int tou = que.front(); que.pop();
if (vis[tou])continue;
vis[tou] = 1;
point1 = tou;
for (int i = head[tou]; i; i = xian[i].next) {
int to = xian[i].to;
if (vis[to])continue;
que.push(to);
}
}
}
void dfs(int now, int fa) {
deep_[now] = deep_[fa] + 1;
father[now] = fa;
md = max(md, deep_[now]);
maxdeppoint[now] = now;
maxdep[now] = deep_[now];
for (int i = head[now]; i; i = xian[i].next) {
int to = xian[i].to;
if (to == fa)continue;
dfs(to, now);
if (maxdep[now] < maxdep[to]) {
maxdep[now] = max(maxdep[now], maxdep[to]);
maxdeppoint[now] = maxdeppoint[to];
}
}
}
int main() {
n = read();
for (int i = 2; i <= n; i++) {
int a = read(), b = read();
add(a, b); add(b, a);
}
bfs();
deep_[0] = -1;
dfs(point1, 0);
for (int i = 1; i <= n; i++) {
if (deep_[i] == md) {
point2 = i; break;
}
}
aim[point2] = 1; aim[point1] = 1;
int now = point2;
while (now != point1){
now = father[now];
aim[now] = 1;
}
for (int i = 1; i <= n; i++) {
if (i != point2 && i != point1) {
point3 = i; break;
}
}
int ans = md,vv = 0;
for (int i = 1; i <= n; i++) {
if (!aim[i] && aim[father[i]]) {
if (vv < maxdep[i] - deep_[father[i]]) {
vv = maxdep[i] - deep_[father[i]];
point3 = maxdeppoint[i];
}
}
}
printf("%d\n%d %d %d",ans + vv,point1 ,point2,point3);
//cout << ans + vv<<endl<<point1 <<" "<<point2<<" "<<point3;
return 0;
}
