题意

求仙人掌的直径(相距最远的两个点的距离)。

\(n\le 5\times 10^4​\)

分析

• 建立圆方树，讨论答案路径的 lca 在圆点还是方点。
• 利用树形 dp 求出每个圆点到 不同子树内圆点 的最长距离与次长距离 \(f_{i,0},f_{i,1}\)。
• 如果答案以某个圆点作为 lca，答案是 \(f_{i,0}+f_{i,1}\) 。
• 否则，将一个方点的圆点子节点拿出来，倍长链后利用单调队列找到最优的两个圆点即可。
• 复杂度 \(O(n)​\) 。

代码

#include
    
     using namespace std;typedef long long LL;#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)#define rep(i, a, b) for(int i = a; i <= b; ++i)#define pb push_back#define re(x) memset(x, 0, sizeof x)inline int gi() {    int x = 0,f = 1;    char ch = getchar();    while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}    while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}    return x * f;}template 
     
       inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}template 
      
        inline bool Min(T &a, T b){return a > b ? a = b, 1 : 0;}const int N = 1e5 + 7;int n, m, edc, dfn, tp, ndc, ans;int low[N], pre[N], stk[N], f[N][2], head[N];vector
       
        G[N];struct edge {    int lst, to;    edge(){}edge(int lst, int to):lst(lst), to(to){}}e[N << 1];void Add(int a, int b) {    e[++edc] = edge(head[a], b), head[a] = edc;    e[++edc] = edge(head[b], a), head[b] = edc;}void tarjan(int u, int fa) {    low[u] = pre[u] = ++dfn;    stk[++tp] = u;    go(u)if(v ^ fa) {        if(!low[v]) {            tarjan(v, u);            Min(pre[u], pre[v]);            if(pre[v] >= low[u]) {                G[u].pb(++ndc);                for(int x = -1; x ^ v; )                G[ndc].pb(x = stk[tp--]);            }        }else Min(pre[u], low[v]);    }}void dfs(int u, int fa) {    if(u <= n) {        for(int i = 0; i < G[u].size(); ++i) dfs(G[u][i], u);    }else {        int res = 0;        for(int i = 0, len = G[u].size(); i < len; ++i) {            int v = G[u][i];            dfs(v, u);            Max(res, f[v][0] + min(i + 1, len - i));        }        if(res > f[fa][0]) {            f[fa][1] = f[fa][0];            f[fa][0] = res;        }else Max(f[fa][1], res);    }}int q[N], val[N];int main() {    n = gi(), m = gi();ndc = n;    rep(i, 1, m) {        int k = gi(), lst = gi();        rep(j, 2, k) {            int x = gi();            Add(x, lst);            lst = x;        }    }    tarjan(1, 0);    dfs(1, 0);    rep(i, 1, n) Max(ans, f[i][0] + f[i][1]);    rep(i, n + 1, ndc) {        int gg = G[i].size();        G[i].pb(0);        for(int j = 0; j < gg; ++j) G[i].pb(G[i][j]);        int hd = 1, tl = 0, len = (gg + 1) / 2;        for(int j = 0; j < G[i].size(); ++j) {            if(j == gg) continue;            int x = G[i][j];            for(; hd <= tl && q[hd] < j - len; ++hd);            if(hd <= tl) Max(ans, f[x][0] + val[hd] + j);            for(; hd <= tl && f[x][0] - j >= val[tl]; --tl);            q[++tl] = j, val[tl] = f[x][0] - j;        }    }    printf("%d\n", ans);    return 0;}