P15099 题解

rainygame · 2026-03-05 15:18:04 · 题解

场上先被 T1 卡两个多小时，拼尽全力写+调出 8k 代码翻盘，结果你跟我说降紫了？？？

首先需要注意到一个关键性质，一个 s 被至少一条 b 路径覆盖，当且仅当去掉这个点之后的连通块中，至少有两个连通块中存在 b 点。

对于一个 s 点 x，找到在操作序列中的后一个点不为 x 的 b 点 u，再找到后一个不为 x 且和 u 不在同一连通块的点 v，那么 [t_x,t_v)（t_v 表示 v 在 x 之后第一次被标为 b 的时间）这段区间就不可能是一个合法区间的右端点（不然 x 这个点就不合法了），每次查询时找到最后一个没有被覆盖的点即可。

先说怎么求出 t_u,t_v，找 t_u 是容易的，就相当于查询 [1,x),(x,n] 区间的最小值，找 t_v 则需要发现去掉 u 这个连通块之后，剩下点形成 O(1) 个 dfs 序上的区间，那么也是可以查询的。

但是覆盖了 [t_x,t_v) 还不够，因为可以发现如果 x 的前面又有一个 b 点被标为 b，且这个点和 u 不在同一连通块中，那么就可以只覆盖 [x,t_u) 了，因此还需要求出 t_x 前面的一对最近的 u,v，然后分讨一下即可。

注意以上都没有考虑一个点同时被标为 s 和 b 的情况，需要特判！

时间复杂度 O(n\log n)。代码实现可能比较复杂，写了两颗线段树，外加一堆分讨。

// #pragma GCC optimize(2, 3, "Ofast")
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXK 17
#define INF 1000000000
typedef pair<int, int> pii;

bool St;

int n, q, ct; int rt[MAXN], fa[MAXK][MAXN], dfn[MAXN], siz[MAXN], dep[MAXN], M[MAXN], ans[MAXN], rs[MAXN], bk[MAXN], pr[MAXN]; pair<int, int> qyy[MAXN];
vector<int> e[MAXN], va[MAXN], vb[MAXN]; struct Que{char c; int x;}que[MAXN]; vector<pair<int, int>> mod[MAXN];

pii meg(pii a, pii b){return {min(a.first, b.first), min(max(a.first, b.first), min(a.second, b.second))};}
pii meg(pii a, int b){return {min(a.first, b), min(max(a.first, b), a.second)};}

void dfs(int x, int f){dep[x] = dep[fa[0][x]=f]+1; dfn[x] = ++ct; siz[x] = 1; for (auto v: e[x]) if (v ^ f) dfs(v, x), siz[x] += siz[v];}
int kth(int x, int k){for (int i(0); i<MAXK; ++i) if (k>>i&1) x = fa[i][x]; return x;}

namespace Seg{
    int tr[MAXN<<2];
    void init(){fill(tr, tr+(MAXN<<2), INF);}
    void mod(int p, int l, int r, int x, int k){
        if (l == r){tr[p] = k; return;} int mid((l+r)>>1);
        if (x <= mid) mod(p<<1, l, mid, x, k); else mod(p<<1|1, mid+1, r, x, k); tr[p] = min(tr[p<<1], tr[p<<1|1]);
    }
    int qry(int p, int l, int r, int L, int R){
        if (L > R) return INF; if (L <= l && r <= R) return tr[p]; int mid((l+r)>>1), res(INF);
        if (L <= mid) res = min(res, qry(p<<1, l, mid, L, R)); if (R > mid) res = min(res, qry(p<<1|1, mid+1, r, L, R)); return res;
    }
}
namespace Seg2{
    pii tr[MAXN<<2]; int tag[MAXN<<2];
    pii meg(pii a, pii b){return a.first == b.first ? max(a, b) : min(a, b);}
    void addtg(int p, int v){tr[p].first += v; tag[p] += v;}
    void push_down(int p){for (; tag[p]; tag[p]=0) addtg(p<<1, tag[p]), addtg(p<<1|1, tag[p]);}
    void bld(int p, int l, int r){if (l == r){tr[p] = {0, l}; return;} int mid((l+r)>>1); bld(p<<1, l, mid); bld(p<<1|1, mid+1, r); tr[p] = meg(tr[p<<1], tr[p<<1|1]);}
    void mod(int p, int l, int r, int L, int R, int k){
        // if (p == 1) cerr << "mod:" << L << ' ' << R << ' ' << k << '\n';
        if (L <= l && r <= R){addtg(p, k); return;} int mid((l+r)>>1); push_down(p);
        if (L <= mid) mod(p<<1, l, mid, L, R, k); if (R > mid) mod(p<<1|1, mid+1, r, L, R, k); tr[p] = meg(tr[p<<1], tr[p<<1|1]);
    }
    pii qry(int p, int l, int r, int L, int R){
        if (L <= l && r <= R) return tr[p]; int mid((l+r)>>1); pii res(INF, 0);
        if (L <= mid) res = meg(res, qry(p<<1, l, mid, L, R)); if (R > mid) res = meg(res, qry(p<<1|1, mid+1, r, L, R)); return res;
    }
}
int kind(int u, int v){if (dep[v] <= dep[u] || kth(v, dep[v]-dep[u]) != u) return -1; return kth(v, dep[v]-dep[u]-1);}

bool Ed;

signed main(){
    // freopen("excite.in", "r", stdin); freopen("excite.out", "w", stdout);
    // cerr << (&Ed-&St)/1024.0/1024.0 << '\n';
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n; for (int i(1), u, v; i<n; ++i) cin >> u >> v, e[u].push_back(v), e[v].push_back(u); dfs(1, 0); cin >> q;
    for (int j(1); j<MAXK; ++j) for (int i(1); i<=n; ++i) fa[j][i] = fa[j-1][fa[j-1][i]];
    // cerr << kind(3, 5) << ' ' << dep[3] << ' ' << dep[5] << '\n';
    // for (int i(1); i<=n; ++i) cerr << dfn[i] << ' '; cerr << '\n';
    for (int i(1); i<=q; ++i){
        cin >> que[i].c >> que[i].x;
        if (que[i].c == 's') va[que[i].x].push_back(i);
        else vb[que[i].x].push_back(i);
        // cerr << que[i].c << ' ' << que[i].x << '\n';
        // (que[i].c == 's' ? va : vb)[que[i].x].push_back(i);
    }
    // cerr << kind(1, 3) << '\n';
    Seg::init();
    for (int i(1); i<=q; ++i){
        if (que[i].c == 's') Seg::mod(1, 1, n, dfn[que[i].x], n-i+1), rs[que[i].x] = i;
        else{
            int u(que[i].x), p(min(Seg::qry(1, 1, n, 1, dfn[u]-1), Seg::qry(1, 1, n, dfn[u]+1, n))); bk[i] = rs[que[i].x];
            // cerr << p << '\n';
            if (p ^ INF){
                p = n-p+1; int v(que[p].x), yyx(kind(u, v)); vector<pair<int, int>> qry;
                if (yyx == -1) qry.push_back({dfn[u]+1, dfn[u]+siz[u]-1});
                else{
                    qry.push_back({1, dfn[u]-1}); qry.push_back({dfn[u]+1, dfn[yyx]-1}); qry.push_back({dfn[yyx]+siz[yyx], n});
                }
                int mnn(INF); for (auto [l, r]: qry) mnn = min(mnn, Seg::qry(1, 1, n, l, r)); qyy[i] = {p, mnn == INF ? INF : n-mnn+1};
                // if (i == 2) cerr << mnn << ' ' << bk[i] << ' ' << yyx << ' ' << v << ' ' << p << '\n';
                if (bk[i]){
                    if (bk[i] >= qyy[i].first) qyy[i] = {INF, INF};
                    else if (bk[i] >= qyy[i].second || qyy[i].second == INF) qyy[i].second = bk[i];
                }
            }else qyy[i] = {INF, INF};
        }
    }
    // cerr << bk[1] << '\n';
    // cerr << "YYX\n";
    Seg::init(); Seg2::bld(1, 1, q); fill(pr+1, pr+n+1, q+1);
    for (int i(q); i; --i){
        // cerr << i << '\n';
        for (auto [l, r]: mod[i]) if (l <= r) Seg2::mod(1, 1, q, l, r, -1);
        if (que[i].c == 's') Seg::mod(1, 1, n, dfn[que[i].x], i), pr[que[i].x] = i;
        else{
            int u(que[i].x), p(min(Seg::qry(1, 1, n, 1, dfn[u]-1), Seg::qry(1, 1, n, dfn[u]+1, n)));
            // cerr << "YYX\n" << p << '\n';
            if (p ^ INF){
                int v(que[p].x), yyx(kind(u, v)); vector<pair<int, int>> qry;
                if (yyx == -1) qry.push_back({dfn[u]+1, dfn[u]+siz[u]-1});
                else{
                    qry.push_back({1, dfn[u]-1}); qry.push_back({dfn[u]+1, dfn[yyx]-1}); qry.push_back({dfn[yyx]+siz[yyx], n});
                }
                int mnn(INF); for (auto [l, r]: qry) mnn = min(mnn, Seg::qry(1, 1, n, l, r));
                if (mnn ^ INF){
                    Seg2::mod(1, 1, q, i, min(mnn, pr[u])-1, 1); int g(kind(u, que[p].x));
                    if (qyy[i].first ^ INF){
                        int v(qyy[i].first); bool fl(kind(u, que[v].x) != g); if (fl) mod[v].push_back({p, min(mnn, pr[u])-1});
                        if (qyy[i].second ^ INF){
                            if (fl) mod[qyy[i].second].push_back({i, min(p, pr[u])-1}); else mod[qyy[i].second].push_back({i, min(mnn, pr[u])-1});
                        }
                    }else if (bk[i]) mod[bk[i]].push_back({i, min(mnn, pr[u])-1});
                }else{
                    // cerr << i << ' ' << qyy[i].first << ' ' << pr[u] << '\n';
                    Seg2::mod(1, 1, q, i, pr[u]-1, 1); int g(kind(u, que[p].x));
                    if (qyy[i].first ^ INF){
                        bool fl(kind(u, que[qyy[i].first].x) != g); if (fl) mod[qyy[i].first].push_back({p, pr[u]-1});
                        // cerr << fl << ' ' << (kind(u, que[qyy[i].first].x) != g) << ' ' << kind(u, que[qyy[i].first].x) << '\n';
                        if (qyy[i].second ^ INF){
                            if (fl) mod[qyy[i].second].push_back({i, min(p, pr[u])-1}); else mod[qyy[i].second].push_back({i, pr[u]-1});
                        }
                    }else if (bk[i]) mod[bk[i]].push_back({i, pr[u]-1});
                }
            }else{
                // cerr << "YYX\n" ;
                // cerr << "g:" << i << '\n';
                Seg2::mod(1, 1, q, i, pr[u]-1, 1);
                // if (i == 2) cerr << qyy[i].first << ' ' << qyy[i].second << '\n';
                // cerr << bk[1] << ' ' << i << ' ' << pr[u]-1 << ' ' << (qyy[i].first == INF) << ' ' << bk[i] << '\n';
                if (qyy[i].first == INF && bk[i]) mod[bk[i]].push_back({i, pr[u]-1});
                if (qyy[i].second ^ INF) mod[qyy[i].second].push_back({i, pr[u]-1});
            }
        }
        auto res(Seg2::qry(1, 1, q, i, q)); ans[i] = res.first ? 0 : res.second-i+1;
        // cerr << res.first << ' ' << res.second << '\n';
    }
    for (int i(1); i<=q; ++i) cout << ans[i] << '\n';

    return 0;
}