题解：P8857 [POI2002] 滑雪者

· · 题解

提供一个 @honglan0301 说的更好的做法。

平面图 Dag 和一个偏序关系是等价的，我们考虑 Dilworth 定理。偏序关系中，最小链覆盖等于最长反链，因此我们想要找最多的没有偏序关系的边。

平面图转对偶图，那么最长反链就是对偶图中从最左边到最右边最长的一个路。题目中给的边是按顺序的，那么我们可以考虑 DP，把平面图中点的信息存在原图中块的右侧的边。

如上图，蓝边为原图的边，红边为对偶图的边，那么红边最长的链砍掉的蓝边就是最长反链，就是答案。

我们设 f_{x} 从最左边到 x 这条边左边的块的最长路，每次不停往上跳，再更新右侧的边的答案。

如上图，绿色使我们 dfs 的路径，6 号点访问过了，那我们就用黄色边 f 的最大值来更新 3 到 5 和 5 到 6 两条边的 f 值。

复杂度是 O(n)。

代码：

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define MP make_pair
#define ep emplace
#define eb emplace_back
//#define int long long
#define rep(i, j, k) for (int i = j; i <= k; i++)
#define per(i, j, k) for (int i = j; i >= k; i--)
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef __int128 lll;
typedef unsigned long long ull;
typedef unsigned int ui;
using namespace std;

int read() {
    int s = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f ^= (c == '-'), c = getchar();
    while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
    return f ? s : -s;
}
int n, tot, in[500005], dp[1000005], vis[500005][2], rev[500005], lst[500005], ans;
vector<pii> e[500005];
void dfs(int u) {
    vis[u][0] = 1;
    for (pii p : e[u]) {
        int v = p.fi, id = p.se;
        if (!vis[v][0]) rev[v] = u, lst[v] = id, dfs(v);
        else {
            int Dp = -1, U = u, V = v;
            while (vis[v][1]) Dp = max(Dp, dp[lst[v]]), v = rev[v];
            Dp++;
            ans = max(ans, Dp);
            dp[id] = Dp;
            while (U != v) dp[lst[U]] = Dp, U = rev[U];
            rev[V] = u, lst[V] = id;
        }
    }
    vis[u][1] = 1;
}

signed main() {
    n = read();
    rep(i, 1, n - 1) {
        for (int cnt = read(); cnt--; ) {
            int x = read();
            in[x]++;
            e[i].eb(x, ++tot);
        }
    }
    dfs(1);
    printf("%d\n", ans + 1);
    return 0;
}