GL: Laminar Family 题解

· · 题解

题目大意

给定一棵 n 个节点的树，给出 m 条路径，试判断下面的命题是否成立：

$1 \leq n,m \leq 10^5

吐槽

这个作业题怎么又是一个数据范围、时间复杂度和时限凑一起越看越离谱的题啊

先有一个 10^6 的小常数线性复杂度题开 10s，这又整一个 O(n \alpha(n)) 的并查集题只开 10^5 还开 3s 的...

题目解法

不难发现，包含关系只可能是短的路径被长的路径包含。

那么我们考虑按照路径长度从小到大一条一条路径边加入边判断。

考虑先将树上的所有边断开，每加入一条路径的时候就将这条路径上包含的边加入，用并查集维护连通块的点数。不难发现，如果加入一条路径后，这条路径所在连通块的点数与当前加入的这条路径上的点数不同时，就必然存在一条路径，与当前加入的这条路径不满足题目所给命题，此时可以判定不成立了。如果加入后点数相符合，那么当前就没有问题。

如果将所有路径都加入了还没出现问题，那么这个命题就可以确定为正确的了。

Code：

const int MAXN = 100010;

int tot;
int fi[MAXN];
int ne[MAXN << 1];
int to[MAXN << 1];

inline void Link(int u, int v) {
    tot++;
    to[tot] = v;
    ne[tot] = fi[u];
    fi[u] = tot;
}

int fa[MAXN];
int dep[MAXN];
int up[MAXN][20];

inline void dfs(int x, int la) {
    dep[x] = dep[la] + 1, up[x][0] = fa[x] = la;
    for(int i = 1; i < 20; i++)
        up[x][i] = up[up[x][i - 1]][i - 1];
    for(int i = fi[x]; i; i = ne[i]) {
        int u = to[i];
        if(u == la) continue;
        dfs(u, x);
    }
}

inline int LCA(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    int k = dep[x] - dep[y];
    for(int i = 0; i < 20; i++)
        if(k & (1 << i)) x = up[x][i];
    if(x == y) return x;
    for(int i = 19; ~i; --i)
        if(up[x][i] != up[y][i])
            x = up[x][i], y = up[y][i];
    return up[x][0];
}

struct Path {
    int u, v, lca, len, id;

    inline void init(int i) {
        id = i, u = ri, v = ri, lca = LCA(u, v);
        len = dep[u] + dep[v] - dep[lca] * 2;
    }

    friend bool operator < (Path a, Path b) { return a.len < b.len; }
}a[MAXN];

struct UFS {
    int fa[MAXN];
    int sz[MAXN];

    inline void init(int n) { for(int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1; }
    inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
    inline void Merge(int u, int v) {
        u = find(u), v = find(v);
        if(u == v) return ;
        fa[u] = v, sz[v] += sz[u];
    }
}ufs;

inline void Solve(Path x) {
    int u, d = dep[x.lca];
    u = ufs.find(x.u); while(dep[u] > d) ufs.Merge(u, fa[u]), u = ufs.find(u);
    u = ufs.find(x.v); while(dep[u] > d) ufs.Merge(u, fa[u]), u = ufs.find(u);
    if(x.len != ufs.sz[ufs.find(x.lca)] - 1) puts("No"), exit(0);
}

int main() {
    int n = ri, m = ri;
    for(int i = 1; i < n; i++) {
        int u = ri, v = ri;
        Link(u, v), Link(v, u);
    } dfs(1, 0);
    for(int i = 1; i <= m; i++) a[i].init(i);
    sort(a + 1, a + 1 + m), ufs.init(n);
    for(int i = 1; i <= m; i++) Solve(a[i]);
    puts("Yes");
    return 0;
}