题解：CF466E Information Graph

· · 题解

题目：CF466E 洛谷链接 CF 链接

模拟赛把 T1 跳了来写这个（T3），离线思路很简单，比 T1 思维题好想。

首先，最终状态是若干颗上下级关系的树，所以我们可以将整个问题放在最后建好的树树上考虑。

对于操作一，将 x 与 y 连边即可。

对于操作二，可以用并查集优化复杂度快速找出当前的最高上司。

对于操作三，我们在每次操作二时把上下两个节点 (u_p, u_d) 储存下来，判断节点 x 是否在路径 i 上可以使用最近公共祖先（LCA），若 \text{LCA}(u_p, x) = u_p \land \text{LCA}(x, u_d) = x，则 x 在路径上，反之则不在。

需要注意的是，最终状态不一定是一棵树，可能有多棵树，在 LCA 初始化时要处理一下。

倍增写 LCA 的话时间复杂度为 O(n \log n)。

赛时代码如下：

namespace dsu {
    int fa[N];
    void init(int n) {
        for(int i = 1; i <= n; i++) fa[i] = i;
    }
    int find(int u) {
        if(fa[u] == u) return u;
        fa[u] = find(fa[u]);
        return fa[u];
    }
    void connect(int u, int v) {
        fa[u] = v;
    }
}
typedef pair<int, int> pii;

vector <int> G[N]; // 存图
int n, m;
vector <pii> ask; // 离线询问
pii cov[N]; // 操作二区间存储
int tp = 0;
int root;
int st[N][20];
int dep[N];
bool vis[N];

void dfs(int u, int f, int d) {
    vis[u] = 1;
    st[u][0] = f;
    dep[u] = d;
    for(int i = 1; i <= 19; i++) st[u][i] = st[ st[u][i - 1] ][i - 1];
    for(auto v : G[u]) {
        if(v == f) continue;
        dfs(v, u, d + 1);
    }
    return;
}
int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    if(u == v) return u;
    for(int i = 19; i >= 0; i--) {
        if(dep[st[u][i]] >= dep[v]) u = st[u][i];
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; i--) {
        if(st[u][i] != st[v][i]) u = st[u][i], v = st[v][i];
    }
    return st[u][0];
}
vector <int> rootl;

int32_t main() {
    n = read(), m = read();
    dsu::init(n);
    while(m--) {
        int opt = read();
        if(opt == -1) break;
        if(opt == 1) {
            int u = read(), v = read();
            dsu::connect(u, v);
            G[u].push_back(v);
            G[v].push_back(u);
            rootl.push_back(v);     
        } else if(opt == 2) {
            int u = read();
            cov[++tp] = {u, dsu::find(u)};
            //cout << "Line: " << tp <<" / "<< u << " -> " << dsu::find(u) << endl;
        } else {
            int u = read(), v = read();
            ask.push_back({u, v});
        }
    }
    for(int i = 1; i <= n; i++) {
        int root = dsu::find(i);
        if(!vis[root])  dfs(root, root, 1);
    }//不止一棵树，有多个根节点要初始化 
    for(auto [x, i]:ask) {
        int upp = cov[i].second, udd = cov[i].first;
        if(dsu::find(x) != dsu::find(upp)) cout << "NO" << endl;
        else if(x == upp || x == udd) cout << "YES" << endl;    
        else cout << (lca(upp, x) == upp && lca(udd, x) == x ? "YES" : "NO") << endl;
    }
    return 0;
}