条了两周了555

用两个堆来弹来弹去

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

constexpr int INF = 0x3f3f3f3f;
int n, q;

//! Strange Data Structure

struct Prio {
    priority_queue<int> rl, rm;
    string name;

    Prio() { }
    Prio(string n) { name = n; }

    int mx() {
        while (1) {
            if (rl.empty())
                return -INF;
            if (rm.empty() || rl.top() != rm.top())
                break;
            rl.pop();
            rm.pop();
        }
        if (rl.empty())
            return -INF;
        else
            return rl.top();
    }

    void insert(int x) {
        // cerr << "> " << name << " insert " << x << endl;
        rl.push(x);
    }

    int remove(int x) {
        // cerr << "> " << name << " remove " << x << endl;
        if (rl.top() == x)
            rl.pop();
        else
            rm.push(x);
    }

    int nx() {
        int maxx = mx();
        if (maxx == -INF)
            return -INF;
        rl.pop();
        int nexx = mx();
        rl.push(maxx);
        return nexx;
    }
};

//! Starch Tree

constexpr int MAXN = 1e5 + 5;

Prio fnl("fnl"), sons[MAXN], father[MAXN];

vector<int> G[MAXN];

int rt, sz[MAXN], all, fa[MAXN], dp[MAXN];
bool vis[MAXN];

void findrt(int u, int pa) {
    int mx = 0;
    sz[u] = 1;
    for (int v : G[u]) {
        if (v == pa || vis[v])
            continue;
        findrt(v, u);
        sz[u] += sz[v];
        mx = max(mx, sz[v]);
    }
    mx = max(mx, all - sz[u]);
    if (mx <= all / 2)
        rt = u;
}

vector<int> vec;

int dis[MAXN][20];

void bfs(int p, int dep) {
    queue<int> q;
    dis[p][dep] = 1;
    q.push(p);
    vec.clear();

    do {
        int u = q.front();
        vec.push_back(u);
        q.pop();
        for (int v : G[u]) {
            if (vis[v])
                continue;
            if (dis[v][dep] > dis[u][dep] + 1) {
                dis[v][dep] = dis[u][dep] + 1;
                q.push(v);
            }
        }
    } while (q.size());
}

int cnt;
int ans[MAXN];
int cl[MAXN];

void build_starch_tree(int u, int dep, int pa) {
    bfs(u, dep);
    all = vec.size();
    findrt(u, 0);
    dp[rt] = dep;
    // cerr << u << " " << dep << ":" << endl;
    // for (int i : vec)
    //     cerr << dis[i][dep] << " ";
    // cerr << endl;
    if (pa)
        for (int i : vec)
            father[rt].insert(dis[i][dep]);

    fa[rt] = pa;
    int now = rt;
    vis[rt] = 1;
    for (int v : G[now])
        if (!vis[v])
            build_starch_tree(v, dep + 1, now);

    if (pa)
        sons[pa].insert(father[now].mx());
    sons[now].insert(0);

    ans[now] = sons[now].mx() + sons[now].nx();
    fnl.insert(ans[now]);
}

void modify(int x) {
    if (cl[x])
        sons[x].remove(0), cnt--;
    else
        sons[x].insert(0), cnt++;
    int u = x;
    while (u) {
        int res = sons[u].mx() + sons[u].nx();
        if (ans[u] != res) {
            fnl.remove(ans[u]);
            ans[u] = res;
            fnl.insert(ans[u]);
        }
        if (!fa[u])
            break;
        int dep = dp[u];
        res = father[u].mx();
        // exit(1);
        if (cl[x])
            father[u].remove(dis[x][dep]);
        else
            father[u].insert(dis[x][dep]);
        int res2 = father[u].mx();
        if (res != res2) {
            sons[fa[u]].remove(res);
            sons[fa[u]].insert(res2);
        }
        u = fa[u];
    }
    cl[x] = !cl[x];
}

//! Main

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        father[i].name = "father[" + to_string(i) + "]";
        sons[i].name = "sons[" + to_string(i) + "]";
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    for (int i = 1; i <= n; i++)
        cl[i] = 1;

    memset(dis, 0x3f, sizeof dis);
    build_starch_tree(1, 0, 0);

    cin >> q;
    cnt = n;

    while (q--) {
        string opt;
        cin >> opt;
        if (opt == "G") {
            if (!cnt)
                cout << -1 << endl;
            else if (cnt == 1)
                cout << 0 << endl;
            else
                cout << fnl.mx() << endl;
        } else {
            int x;
            cin >> x;
            modify(x);
        }
    }

    return 0;
}