70pts求助

rt，WA on #1000 ~ #40000 行，n \le 1000 过 500 组拍

#include <bits/stdc++.h>
using namespace std;

inline void train() {
       ios::sync_with_stdio(false);
       cin.tie(0);
       cout.tie(0);
}

inline int maxi(int a, int b) {
    return a > b ? a : b;
}

inline int mini(int a, int b) {
    return a < b ? a : b;
}

constexpr int N = 5e5+4, LN = 800004*4, M = 5e5+4;

vector<int> tree[N];

struct edge {
    int to, id;
    edge() {

    }
    edge(int to) : to(to) {

    }
    edge(int to, int id) : to(to), id(id) {

    }
};

priority_queue<edge> pq;
bool operator < (const edge &a, const edge &b) {
    return a.id < b.id;
}

vector<edge> graph[N], gentree[N];
int n, m, q, tid, father[N], ax[M], bx[M], save[M], depth[N], enable_when[N], target[N];
int cover[N], fas[N][20];
char otype[N];
int us[N], vs[N];
bool ans[N];
bool vis[N];

struct dset {
    dset() {

    }

    int fa[N], sz[N];

    inline void init(const int& n) {
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
            sz[i] = 1;
        }
    }
    int query(const int& x) {
        return x == fa[x] ? x : fa[x] = query(fa[x]);
    }

    inline void merge(const int& a, const int& b) {
        int qa = query(a), qb = query(b);
        if (qa == qb) return;
        if (sz[qa] < sz[qb]) swap(qa, qb);
        fa[qb] = qa;
        sz[qa] += sz[qb];
    }
};

dset tarjan, complete, gens;

void dfs(int cur, int fa) {
//  cerr << fa << " -> " << cur << endl;
    depth[cur] = depth[fa] + 1;
    father[cur] = fa;
    for (auto &i : tree[cur]) {
        if (i == fa) continue;
        dfs(i, cur);
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    int diff = depth[a] - depth[b];
    for (int i = 1<<19, bs = 19; i >= 1; i >>= 1, bs--) {
        if (diff & i) a = fas[a][bs];
    }
    if (a == b) return a;
    while (father[a] != father[b]) {
        int step = 19;
        for (; step >= 0 && fas[a][step] == fas[b][step]; step--);
        if (step < 0) return father[a];
        a = fas[a][step];
        b = fas[b][step];
    }
    return father[a];
}

void icover(int a, int l, int s) {
    int x = a;
    while (depth[a] > depth[l]) {
        cover[a]++;
        if (cover[a] > 1) tarjan.merge(a, l);
//      cerr << "Executed to " << a << ", covering " << cover[a] << endl;
        a = father[target[a]];
    }
    while (depth[x] > depth[l]) {
        int tmp = father[target[x]];
        if (cover[x] > 1) target[x] = a;
        x = tmp;
    }
}

void covering(int a, int b) {
    int l = lca(a, b);
//  cerr << "Covering " << a << " and " << b << ", LCA = " << l << endl;
    icover(a, l, a);
//  cerr << "===\n";
    icover(b, l, a);
//  cerr << endl;
}

set<pair<int, int> > edges;
map<pair<int, int>, int> ids;

void dfs1(int cur, int fa) {
    vis[cur] = true;
    for (auto &i : graph[cur]) {
        pq.push(edge(i.id, save[i.id]));
        if (vis[i.to]) continue;
        dfs1(i.to, cur);
    }
}

int main() {

    train();

    cin>>n>>m>>q;
    tarjan.init(n); complete.init(n); gens.init(n);
    for (int i = 1; i <= m; i++) {
        cin>>ax[i]>>bx[i];
        int a = ax[i], b = bx[i];
        graph[ax[i]].push_back(edge(bx[i], i));
        graph[bx[i]].push_back(edge(ax[i], i));
        auto ap = make_pair(mini(a,b),maxi(a,b));
        edges.insert(ap);
        save[i] = q+1;
        ids[ap] = i;
        complete.merge(ax[i], bx[i]);
    }
    for (int i = 1; i <= q; i++) {
        cin>>otype[i]>>us[i]>>vs[i];
        int a = us[i], b = vs[i];
        if (otype[i] == 'Z') {
            auto ap = make_pair(mini(a,b),maxi(a,b));
            edges.erase(ap);
            save[ids[ap]] = i;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (complete.query(i) == i) {
            // Generate a tree:
            dfs1(i, i);
//          cerr << "Construct tree for " << i << endl;
            int cnt = 0;
            while ((cnt <= complete.sz[i]) && (!pq.empty())) {
                edge pt = pq.top();
                pq.pop();
                if (gens.query(ax[pt.to]) == gens.query(bx[pt.to])) continue;
                tree[ax[pt.to]].emplace_back(bx[pt.to]);
                tree[bx[pt.to]].emplace_back(ax[pt.to]);
//              cerr << ax[pt.to] << " <-> " << bx[pt.to] << endl;
                cnt++;
                gens.merge(ax[pt.to], bx[pt.to]);
            }
            while (!pq.empty()) pq.pop();
            dfs(i, i);
        }
        target[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        target[i] = i;
        fas[i][0] = father[i];
    }
    for (int step = 1; step < 20; step++) {
        for (int i = 1; i <= n; i++) fas[i][step] = fas[fas[i][step-1]][step-1]; 
    }
    for (auto &i : edges) covering(i.first, i.second);
    for (int i = q; i >= 1; i--) {
        switch (otype[i]) {
            case 'Z':
                // Do the cover
                covering(us[i], vs[i]);
                break;
            case 'P':
                ans[i] = (tarjan.query(us[i]) == tarjan.query(vs[i]));
                break;
        }
    }
    for (int i = 1; i <= q; i++) {
        if (otype[i] == 'P') {
            if (ans[i]) cout<<"TAK\n";
            else cout<<"NIE\n";
        }
    }

    cout<<flush;

    return 0;
}