1180번: Cactus Reloaded

https://www.acmicpc.net/problem/1180

#include<cstdio>
#include<vector>
#include<deque>
#include<algorithm>
using namespace std;
const int MXN = 5e4;
int n, m, vis[MXN + 1], res, d[MXN + 1], cks[MXN + 1];
vector<int> adj[MXN + 1], stk;
vector<vector<int> > cyc[MXN + 1];
void f(int h, int p) {
    vis[h]++;
    cks[h]++;
    stk.push_back(h);
    for (auto it : adj[h]) if (it^p) {
        if (cks[it]) {
            vector<int> v = { 0 };
            for (int i = stk.size(); stk[--i] ^ it;) v.push_back(stk[i]), vis[stk[i]]++;
            cyc[it].push_back(v);
        }
        if (!vis[it]) f(it, h);
    }
    if (p&&vis[h] == 1) cyc[p].push_back({ 0,h });
    stk.pop_back();
    cks[h]--;
}
void g(int h) {
    int m1 = 0, m2 = 0;
    for (auto c : cyc[h]) {
        deque<pair<int, int> > dq;
        for (int i = 1; i < c.size(); i++) {
            g(c[i]);
            m2 = max(m2, d[c[i]] + min(i, int(c.size()) - i));
        }
        for (int i = c.size() / 2; i < c.size(); i++) {
            while (!dq.empty() && dq.back().second < d[c[i]] + c.size() - i) dq.pop_back();
            dq.push_back({ i - c.size(), d[c[i]] + c.size() - i });
        }
        for (int i = 0; i < c.size(); i++) {
            if (i - dq.front().first>c.size() / 2) dq.pop_front();
            res = max(res, d[c[i]] + dq.front().second + i);
            while (!dq.empty() && dq.back().second < d[c[i]] - i) dq.pop_back();
            dq.push_back({ i,d[c[i]] - i });
        }
        if (m1 < m2) swap(m1, m2);
    }
    res = max(res, m1 + m2);
    d[h] = m1;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, k, x, y; i < m; i++) {
        scanf("%d%d", &k, &x);
        for (int i = 1; i < k; i++) {
            scanf("%d", &y);
            adj[x].push_back(y);
            adj[y].push_back(x);
            x = y;
        }
    }
    f(1, 0);
    g(1);
    printf("%d", res);
    return 0;
}