HNOI 2016 Day1 简略题解

Published on 2016-04-19

最小公倍数 multiple

待补
Menci

网络 network

对于每个通讯 (u,v,w)(u, v, w) 我们可以发现,所有在路径 uvu\rightarrow v 上的点均不能取到 ww,其余的点均可以取到 ww
于是用 DFS 序版本的树链剖分,每个节点维护一个大根堆,对于通讯 (u,v)(u, v),我们剖出 O(logn)O(\log n) 个区间,所以在 DFS 序上面的补区间也是 O(logn)O(\log n) 的,在这些区间上进行修改,删除就可以了。
注意要运用标记永久化的思想,即如果当前区间被完全包含,那么直接在该节点所对应的堆上面直接操作,经过这个节点的查询要顺便取上这个节点的最大值。而一旦删除,删除的肯定还是之前加过的那些区间,所以这个标记永久化是可行的!
复杂度:O(nlog3n)O(n\log^3 n),实测常数小。

//  Created by Sengxian on 4/19/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 4537 HNOI 2016 Day1 T2 网络 network
#include <algorithm>
#include <iostream>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#define mid (((l) + (r)) / 2)
#define ls o * 2 + 1
#define rs o * 2 + 2
using namespace std;
const int maxn = 100000 + 3, maxm = 200000 + 3;
vector<int> G[maxn];
int n, m, qu[maxm], qv[maxm], qw[maxm];

inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

typedef pair<int, int> interval;
vector<interval> intervals;
namespace tree_chain_split {
    int bel[maxn], dfn[maxn], depth[maxn], fa[maxn], s[maxn], timestamp = 0;
    int dfs1(int u) {
        s[u] = 1;
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa[u]) {
                fa[v] = u, depth[v] = depth[u] + 1;
                s[u] += dfs1(v);
            }
        }
        return s[u];
    }
    void dfs2(int u, int num) {
        dfn[u] = timestamp++, bel[u] = num;
        int Max = 0, idx = -1;
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa[u] && s[v] > Max) Max = s[idx = v];
        }
        if (Max == 0) return;
        dfs2(idx, num);
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa[u] && v != idx) dfs2(v, v);
        }
    }
    inline void get_path_interval(int a, int b) {
        intervals.clear();
        while (bel[a] != bel[b]) {
            if (depth[bel[a]] < depth[bel[b]]) swap(a, b);
            intervals.push_back(interval(dfn[bel[a]], dfn[a] + 1));
            a = fa[bel[a]];
        }
        if (dfn[a] > dfn[b]) swap(a, b);
        intervals.push_back(interval(dfn[a], dfn[b] + 1));
    }
}

using namespace tree_chain_split;
template <typename T>
struct Rint {
    bool operator ()(const T &l, const T &r) const {return l > r;}
};
struct Heap {
    priority_queue<int> add, del;
    inline void insert(int x) {add.push(x);}
    inline void erase(int x) {del.push(x);}
    inline int top() {
        while (add.size() && del.size() && add.top() == del.top()) add.pop(), del.pop();
        return add.top();
    }
};

namespace segment_tree {
    Heap heap[(1 << 17) * 2 + 3];
    void build(int o, int l, int r) {
        heap[o].insert(-1);
        if (r - l > 1) build(ls, l, mid), build(rs, mid, r);
    }
    void modify(int o, int l, int r, int a, int b, int v, bool flag) {
        if (l >= a && r <= b) {
            if (flag) heap[o].insert(v);
            else heap[o].erase(v);
        }else {
            if (mid > a) modify(ls, l, mid, a, b, v, flag);
            if (mid < b) modify(rs, mid, r, a, b, v, flag);
        }
    }
    int query(int o, int l, int r, int v) {
        if (r - l == 1) return heap[o].top();
        else if (v < mid) return max(heap[o].top(), query(ls, l, mid, v));
        else return max(heap[o].top(), query(rs, mid, r, v));
    }
}
using namespace segment_tree;

inline void modify(int a, int b, int v, bool flag) {
    get_path_interval(a, b);
    sort(intervals.begin(), intervals.end());
    int last = 0;
    for (int i = 0; i < (int)intervals.size(); ++i) {
        modify(0, 0, n, last, intervals[i].first, v, flag);
        last = intervals[i].second;
    }
    if (last < n) modify(0, 0, n, last, n, v, flag);
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("test.in", "r", stdin);
    #endif
    n = ReadInt(), m = ReadInt();
    for (int i = 0; i < n - 1; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1;
        G[f].push_back(t);
        G[t].push_back(f);
    }
    fa[0] = -1, depth[0] = 0, dfs1(0), dfs2(0, 0);
    build(0, 0, n);
    for (int i = 0; i < m; ++i) {
        int type = ReadInt();
        if (type == 0) {
            qu[i] = ReadInt() - 1, qv[i] = ReadInt() - 1, qw[i] = ReadInt();
            modify(qu[i], qv[i], qw[i], 1);
        } else if (type == 1) {
            int t = ReadInt() - 1;
            modify(qu[t], qv[t], qw[t], 0);
        } else if (type == 2) printf("%d\n", query(0, 0, n, dfn[ReadInt() - 1]));
    }
    return 0;
}

还有一种做法,不过我写了 300+ 行,还是没写出来,而且常数巨大。
对于每个询问,二分答案。则问题转化成:
设二分的答案为 KK,判断所有权值 >K>K 的路径是否都经过服务器 xx 。如果都经过,则答案 K\le K;否则 >K>K
实际上只需要对所有权值 >K>K 的路径求 路径交。
路径的交集依然是路径,用 RMQ 求 LCA 的话,在 O(1)O(一两百) 的时间内就可以求出两条路径的交集。
那用平衡树,或者离线离散化后用线段树,按权值的大小来维护二分结构就好。
时间复杂度 O(mlogn100)O(m\log n \cdot 100)

哪位神犇有比较好的路径并,求告知 QQ:柒零零捌零玖叁
代码放在最后。

树 tree

超级码农题,听说 Fuxey 考试 400+ 行写错两行直接变 30,可惜了。
我们把大树看成一个个块组成的树。一开始大树只有一个块,即模版树。每个插入相当于插入一个块,要记录它的在模版树里面的父亲以及在大树里面的父亲。而块与块之间的距离定义为块的根到另一个块的根的距离。查询两个点的距离,也就是要实现:

  1. 查大树中两个点的 LCA。
  2. 查大树中某点深度。

那么大树中 (u,v)(u, v) 距离就是 ,如果用倍增/树剖维护这些块的话,这两个操作都是可以轻松实现的。
细节就是需要知道某一节点在哪个块,这个可以二分找。还需要知道大树中的节点对应模版树哪个节点,所以我们要用主席树维护模版树,找第 KK 大。

//  Created by Sengxian on 4/19/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 4537 HNOI 2016 Day1 T3 树
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#define mid (((l) + (r)) / 2)
using namespace std;


typedef long long ll;
inline ll ReadLL() {
    static int ch;
    static ll n;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 100000 + 3, maxm = 100000 + 3;
vector<int> G[maxn];
int n, m, q, fa[maxn], dfn[maxn], depth[maxn], s[maxn];

namespace president_tree {
    struct seg_node *null;
    struct seg_node {
        seg_node *ls, *rs;
        int sum;
        inline void maintain() {sum = ls->sum + rs->sum;}
    }*root[maxn];
    seg_node* modify(const seg_node *o, int l, int r, int p) {
        seg_node *ne = new seg_node(); *ne = *o;
        if (r - l == 1) ne->sum++;
        else {
            if (p < mid) ne->ls = modify(ne->ls, l, mid, p);
            else ne->rs = modify(ne->rs, mid, r, p);
            ne->maintain();
        }
        return ne;
    }
    int query(const seg_node *o1, const seg_node *o2, int l, int r, int a, int b) {
        if (l >= a && r <= b) return o2->sum - o1->sum;
        else {
            int ret = 0;
            if (mid > a) ret += query(o1->ls, o2->ls, l, mid, a, b);
            if (mid < b) ret += query(o1->rs, o2->rs, mid, r, a, b);
            return ret;
        }
    }
    int find_kth(const seg_node *o1, const seg_node *o2, int l, int r, int k) {
        if (r - l == 1) return l;
        if (o2->ls->sum - o1->ls->sum >= k) return find_kth(o1->ls, o2->ls, l, mid, k);
        else return find_kth(o1->rs, o2->rs, mid, r, k - (o2->ls->sum - o1->ls->sum));
    }
    int timestamp = 0, timestamp1 = 0, dfs_seq[maxn * 2], dfn1[maxn];
    int dfs(int u) {
        root[timestamp] = modify(timestamp ? root[timestamp - 1] : null, 0, n, u);
        dfn[u] = timestamp++, s[u] = 1;
        dfn1[u] = timestamp1, dfs_seq[timestamp1++] = u;
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa[u]) depth[v] = depth[u] + 1, fa[v] = u, s[u] += dfs(v), dfs_seq[timestamp1++] = u;
        }
        return s[u];
    }
}

using namespace president_tree;
namespace RMQ {
    int minv[maxn * 2][20];
    inline bool cmp(const int &a, const int &b) {
        return depth[a] < depth[b];
    }
    inline void process() {
        for (int i = 0; i < n * 2 - 1; ++i) minv[i][0] = dfs_seq[i];
        for (int w = 1; (1 << w) < n * 2; ++w)
            for (int i = 0; (1 << w) + i < n * 2; ++i)
                minv[i][w] = min(minv[i][w - 1], minv[i + (1 << (w - 1))][w - 1], cmp);
    }
    inline int LCA(int a, int b) {
        a = dfn1[a], b = dfn1[b];
        if (a > b) swap(a, b);
        int bit = log2(b - a + 1);
        return min(minv[a][bit], minv[b - (1 << bit) + 1][bit], cmp);
    }
    inline int length(int a, int b) {
        return depth[a] + depth[b] - 2 * depth[LCA(a, b)];
    }
}
using namespace RMQ;


inline int find_kth(int u, int k) {
    return find_kth(u ? root[dfn[u] - 1] : null, root[dfn[u] + s[u] - 1], 0, n, k);
}

ll blocks[maxm]; //记录块
int block_root[maxm]; //块在模版树中的根
ll block_broot[maxn]; //块在大树中的根
ll block_dr[maxm]; //块的根到大树根的距离
int block_dep[maxm]; //块到根要跨越几个块
int block_anc[maxm][20]; //向上 2 ^ i 个块的编号
ll block_fa[maxm][20]; //向上 2 ^ i 个块的到达的标号
int sz = 0;

inline int getBel(ll idx) {
    return upper_bound(blocks, blocks + sz, idx) - blocks;
}

void process() {
    for (int w = 1; (1 << w) < sz; ++w)
        for (int i = 0; i < sz; ++i)
            if (block_dep[i] - (1 << w) >= 0) {
                block_anc[i][w] = block_anc[block_anc[i][w - 1]][w - 1];
                block_fa[i][w] = block_fa[getBel(block_fa[i][w - 1])][w - 1];
            }
}

//获得块 bel 中模版树编号为 u 在大树中的标号
inline ll getID(int u, int bel) {
    int o = block_root[bel];
    return query(o ? root[dfn[o] - 1] : null, root[dfn[o] + s[o] - 1], 0, n, 0, u) + (!bel ? 0 : blocks[bel - 1]);
}

//获得块 bel 中大树中编号为 u 在模版树中的标号
inline int reID(ll u, int bel) {
    if (bel == 0) return u;
    return find_kth(block_root[bel], u - (!bel ? 0 : blocks[bel - 1]) + 1); //这是第几大,所以要 +1
}

inline int dist_in_one_block(ll a, ll b, int bel = -1) {
    if (bel == -1) bel = getBel(a);
    return length(reID(a, bel), reID(b, bel));
}

//a 到大树根的距离
inline ll dep(ll a) {
    int bel = getBel(a);
    return dist_in_one_block(a, block_broot[bel]) + block_dr[bel];
}

//大树中 (a, b) 的 LCA
inline ll lca(ll a, ll b) {
    int a_bel = getBel(a), b_bel = getBel(b);
    if (block_dep[a_bel] < block_dep[b_bel]) swap(a_bel, b_bel), swap(a, b);
    for (int i = log2(block_dep[a_bel]); i >= 0; --i)
        if (block_dep[a_bel] - (1 << i) >= block_dep[b_bel])
            a = block_fa[a_bel][i], a_bel = block_anc[a_bel][i];
    if (a_bel == b_bel) return getID(LCA(reID(a, a_bel), reID(b, a_bel)), a_bel);
    for (int i = log2(block_dep[a_bel]); i >= 0; --i)
        if (block_dep[a_bel] - (1 << i) >= 0 && block_anc[a_bel][i] != block_anc[b_bel][i])
            a = block_fa[a_bel][i], a_bel = block_anc[a_bel][i],
            b = block_fa[b_bel][i], b_bel = block_anc[b_bel][i];;
    a = block_fa[a_bel][0], a_bel = block_anc[a_bel][0],
    b = block_fa[b_bel][0], b_bel = block_anc[b_bel][0];
    return getID(LCA(reID(a, a_bel), reID(b, a_bel)), a_bel);
}

inline ll query(ll a, ll b) {
    return dep(a) + dep(b) - 2 * dep(lca(a, b));
}


int main() {
    null = new seg_node(), null->sum = 0, null->ls = null, null->rs = null;
    n = ReadInt(), m = ReadInt(), q = ReadInt();
    for (int i = 0; i < n - 1; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1;
        G[f].push_back(t), G[t].push_back(f);
    }
    fa[0] = -1, dfs(0), RMQ::process();
    blocks[sz++] = n;
    block_root[0] = 0, block_broot[0] = 0, block_dep[0] = 0, block_dr[0] = 0;
    for (int i = 1; i <= m; ++i) {
        block_root[i] = ReadInt() - 1;
        int u = block_root[i];
        blocks[sz++] = blocks[i - 1] + s[u];
        block_broot[i] = getID(u, i);
        block_fa[i][0] = ReadLL() - 1;
        block_anc[i][0] = getBel(block_fa[i][0]);
        block_dr[i] = block_dr[block_anc[i][0]] + dist_in_one_block(block_fa[i][0], block_broot[block_anc[i][0]], block_anc[i][0]) + 1;
        block_dep[i] = block_dep[block_anc[i][0]] + 1;
    }
    ::process();
    for (int i = 0; i < q; ++i)
        printf("%lld\n", query(ReadLL() - 1, ReadLL() - 1));
}

T2的不好代码:

//  Created by Sengxian on 4/18/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 4538 HNOI 2016 Day1 T2 network
#include <algorithm>
#include <iostream>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
#define mid (((l) + (r)) / 2)
using namespace std;

inline int ReadInt() {
    static int n, ch;
    static bool flag;
    n = 0, ch = getchar(), flag = false;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return flag ? -n : n;
}

const int maxn = 100000 + 30, maxm = 200000 + 30;
vector<int> G[maxn];
int n, m;

struct Path {
    int s, t;
    bool empty;
    Path(int s = 0, int t = 0): s(s), t(t), empty(false) {}
    void print() {
        if (empty) puts("empty");
        else printf("%d->%d\n", s + 1, t + 1);
    }
};

namespace lca {
    int dfsSeq[maxn * 2], dfn1[maxn], dfn[maxn], depth[maxn], minv[maxn * 2][20], timestamp = 0, timestamp1 = 0;
    int s[maxn], dr[maxn];
    int dfs(int u, int fa) {
        depth[u] = fa == -1 ? 0 : depth[fa] + 1;
        dfn1[u] = timestamp, dfsSeq[timestamp++] = u, dfn[u] = timestamp1++;
        s[u] = 1;
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa) {
                dr[v] = dr[u] + 1;
                s[u] += dfs(v, u);
                dfsSeq[timestamp++] = u;
            }
        }
        return s[u];
    }
    inline bool cmp(const int &a, const int &b) {
        return depth[a] < depth[b];
    }
    void process() {
        dr[0] = 0;
        dfs(0, -1);
        for (int i = 0; i < 2 * n - 1; ++i) minv[i][0] = dfsSeq[i];
        for (int w = 1; (1 << w) < 2 * n; ++w) //[0, 2 * n - 1)
            for (int i = 0; i < 2 * n - 1; ++i)
                if (i + (1 << w) < 2 * n) minv[i][w] = min(minv[i][w - 1], minv[i + (1 << (w - 1))][w - 1], cmp);
    }
    inline bool in(int x, int l, int r) {
        return x >= l && x < r;
    }
    inline int LCA(int a, int b) {
        a = dfn1[a], b = dfn1[b];
        if (a > b) swap(a, b);
        int bit = log2(b - a + 1);
        return min(minv[a][bit], minv[b - (1 << bit) + 1][bit], cmp);
    }
    inline int length(int u, int v) {
        return dr[u] + dr[v] - 2 * dr[LCA(u, v)];
    }
    //判断 u -> v 是否经过 t
    inline bool judge(const Path &p, int t) {
        if (p.empty) return false;
        if (p.s == n && p.t == n) return true;
        static int u, v;
        u = p.s, v = p.t;
        if (u == t || v == t) return true;
        if (in(dfn[u], dfn[t], dfn[t] + s[t]) != in(dfn[v], dfn[t], dfn[t] + s[t])) return true;
        if (LCA(u, v) == t) return true;
        return false;
    }
}

using namespace lca;

inline int len(const Path &a, int s, int t) {
    int l1 = length(a.s, s), l2 = length(a.s, t);
    if (l1 > l2) swap(l1, l2), swap(s, t);
    return l1 + length(a.t, t);
}

Path inter(Path a, Path b) {
    if (a.s == n && a.t == n) return b;
    if (b.s == n && b.t == n) return a; //null 节点特判
    if (dfn[a.s] > dfn[a.t]) swap(a.s, a.t);
    if (dfn[b.s] > dfn[b.t]) swap(b.s, b.t);
    vector<int> k;
    k.push_back(LCA(a.s, a.t)), k.push_back(LCA(a.s, b.s));
    k.push_back(LCA(a.s, b.t)), k.push_back(LCA(a.t, b.s));
    k.push_back(LCA(a.t, b.t)), k.push_back(LCA(b.s, b.t));
    sort(k.begin(), k.end());
    k.erase(unique(k.begin(), k.end()), k.end());
    Path p; p.empty = true;
    int nowLen = 0;
    for (int i = 0; i < (int)k.size(); ++i)
        for (int j = i; j < (int)k.size(); ++j) {
            int s = k[i], t = k[j];
            if (dfn[s] > dfn[t]) swap(s, t);
            int l = length(s, t);
            if (len(a, s, t) + l == length(a.s, a.t) && 
                len(b, s, t) + l == length(b.s, b.t) && l > nowLen) {
                nowLen = l;
                p.s = s, p.t = t;
                p.empty = false;
            }
        }
    return p;
}

struct Treap *pit, *null;
struct Treap {
    int key, val, s;
    Path path, interpath;
    Treap *fa, *ls, *rs;
    inline void maintain() {
        s = ls->s + rs->s + 1;
        interpath = inter(inter(ls->interpath, rs->interpath), path);
    }
}*root, *troot[maxm];
Treap* newNode(int key, int s, int t, int val = rand()) {
    pit = new Treap();
    pit->key = key, pit->val = val, pit->s = 1, pit->ls = pit->rs = null;
    pit->path.s = s, pit->path.t = t, pit->path.empty = false, pit->fa = null;
    pit->interpath.s = s, pit->interpath.t = t, pit->interpath.empty = false;
    return pit;
}
Treap* merge(Treap *a, Treap *b) {
    if (a == null) return b;
    if (b == null) return a;
    if (a->val < b->val) {
        a->rs = merge(a->rs, b);
        a->rs->fa = a;
        a->maintain();
        return a;
    }else {
        b->ls = merge(a, b->ls);
        b->ls->fa = b;
        b->maintain();
        return b;
    }
}

typedef pair<Treap*, Treap*> Droot;
Droot split(Treap *o, int k) {
    Droot d(null, null);
    if (o == null) return d;
    int s = o->ls->s;
    if (k <= s) {
        d = split(o->ls, k);
        o->ls = d.second;
        o->ls->fa = o;
        o->maintain();
        d.second = o;
    } else {
        d = split(o->rs, k - s - 1);
        o->rs = d.first;
        o->rs->fa = o;
        o->maintain();
        d.first = o;
    }
    d.first->fa = null, d.second->fa = null;
    return d;
}

int getKth(const Treap *o, int v) {
    if (o == null) return 0;
    return v <= o->key ? getKth(o->ls, v) : getKth(o->rs, v) + o->ls->s + 1;
}

int findKth(const Treap *o, int k) {
    if (o == null || k <= 0 || k > o->s) return 0;
    int s = o->ls->s;
    if (s + 1 == k) return o->key;
    else if (k <= s) return findKth(o->ls, k);
    else return findKth(o->rs, k - s - 1);
}
void insert(int s, int t, int v) {
    int k = getKth(root, v);
    Droot l = split(root, k);
    root = merge(merge(l.first, newNode(v, s, t)), l.second);
}
void del(Treap *o) {
    int k = o->ls->s;
    while (o->fa != null) {
        if (o->fa->rs == o) k += o->fa->ls->s + 1;
        o = o->fa;
    }
    Droot l = split(root, k), r = split(l.second, 1);
    root = merge(l.first, r.second);
}

void print(const Treap *o) {
    if (o == null) return;
    print(o->ls);
    printf("%d: %d %d\n", o->key, o->path.s + 1, o->path.t + 1);
    print(o->rs);
}

int go(const Treap *o, int x) {
    if (!judge(o->rs->interpath, x)) {
        assert(o->rs != null);
        return go(o->rs, x);
    }
    else if (o->key == -1 || !judge(o->path, x)) return o->key;
    else {
        assert(o->ls != null);
        return go(o->ls, x);
    }
}

void solve(int x) {
    printf("%d\n", go(root, x));
}

int main() {
    n = ReadInt(), m = ReadInt();
    for (int i = 0; i < n - 1; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1;
        G[f].push_back(t);
        G[t].push_back(f);
    }
    process();
    null = newNode(0, 0, 0);
    null->fa = null, null->s = 0, null->interpath.s = n, null->interpath.t = n, root = null;
    null->path.s = n, null->path.t = n;
    null->ls = null->rs = null;
    insert(n, n, -1);
    for (int i = 0; i < m; ++i) {
        int type = ReadInt();
        if (type == 0) {
            int a = ReadInt() - 1, b = ReadInt() - 1, v = ReadInt();
            insert(a, b, v);
            troot[i] = pit;
        } else if (type == 1) {
            int t = ReadInt() - 1;
            del(troot[t]);
        } else solve(ReadInt() - 1);
    }
    return 0;
}