A102291 线性做法

看到很多人用二分，这里提供一个线性做法。

首先求出树的直径，设直径长度为 $d$，然后再在直径的正数和倒数第 $\lfloor \frac{d}{4} \rfloor + \lfloor \frac{d \bmod 4}{2} \rfloor + 1$ 个放上去两个中心，然后枚举一下直径上这两个点之间的节点除直径外引出去的最长链的长度加上它到两个中心的距离的最小值，取最大值，这个最大值与 $\lfloor \frac{d}{4} \rfloor + \lfloor \frac{d \bmod 4}{2} \rfloor$ 的平均值向上取整既为所求，因为两个中心可以往直径里缩，证明较为简单。

代码：

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a),END##i=(b);i<=END##i;++i)
#define pre(i,a,b) for(int i=(a),END##i=(b);i>=END##i;--i)
#define BY_MLE_Automaton chaoxikechi
#define INF 0x3f3f3f3f
#define llINF 0x3f3f3f3f3f3f3f3f
#define mem(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

int n, dis[200005], f[200005], mx; vector<int> g[200005], dp;
void dfs(int u, int fa1, int fa2)
{
	mx = max(mx, dis[u] = dis[fa1] + 1);
    f[u] = fa1;
	for (auto v : g[u]) if (v != fa1 && v != fa2) dfs(v, u, 0);
}
int main()
{
	scanf("%d", &n);
	rep(i, 2, n)
	{
		int u, v; scanf("%d%d", &u, &v);
		g[u].push_back(v); g[v].push_back(u);
	}
	dfs(1, 0, 0); int t = max_element(dis + 1, dis + n + 1) - dis;
	mem(dis, 0); dfs(t, 0, 0);
    int di = max_element(dis + 1, dis + n + 1) - dis, tdi = di, dl = dis[di] - 1;
    while (tdi != t)
    {
        dp.push_back(tdi);
        tdi = f[tdi];
    }
    dp.push_back(t);
    int ai = dl / 4 + dl % 4 / 2, bi = 0;
    int pa = ai, pb = dl - ai;
    rep(i, pa + 1, pb - 1)
    {
        dis[dp[i - 1]] = -1; mx = 0;
        dfs(dp[i], dp[i - 1], dp[i + 1]);
        bi = max(bi, mx + min(i - pa, pb - i));
    }
    printf("%d\n", (ai + bi + 1) / 2);
    return 0;
}

彩蛋：把 $\lfloor \frac{d}{4} \rfloor + \lfloor \frac{d \bmod 4}{2} \rfloor$ 写成 $\lfloor \frac{d}{3} \rfloor + \lfloor \frac{d \bmod 3}{2} \rfloor$ 能得到 $95\ pts$ 的高分。