Sengxian's Blog

//  Created by Sengxian on 3/17/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Spoj QTREE V 链分治
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
using namespace std;

inline int ReadInt() {
    int 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, INF = 0x3f3f3f3f;
vector<int> G[maxn];
int n = 0, blackCnt = 0;
bool color[maxn]; // 0 - black 1 - white

//datas
int fa[maxn], s[maxn], id[maxn], idR[maxn], bel[maxn], timestamp = 0, sz[maxn]; //sz[i] 为以 i 为根的线段树的大小
int root[maxn]; //链头的线段树节点标号
//end

//seg dates
static const int maxNode = (1 << 17) * 2 + 10;
struct Node {
    int minL, minR;
    Node(int minL = INF, int minR = INF): minL(minL), minR(minR) {} 
}segs[maxNode];
int ls[maxNode], rs[maxNode];
int segCnt = 0;
//end
multiset<int> ch[maxn];

int dfs1(int u, int f) {
    fa[u] = f, s[u] = 1;
    for (int i = 0; i < (int)G[u].size(); ++i) {
        int v = G[u][i];
        if (v != f) s[u] += dfs1(v, u);
    }
    return s[u];
}

void dfs2(int u, int num) {
    idR[timestamp] = u, id[u] = timestamp++, bel[u] = num;
    sz[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[v], 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);
    }
}

Node merge(const Node &lnode, const Node &rnode, int l, int r) {
    int mid = (l + r) / 2;
    Node newNode;
    newNode.minL = min(lnode.minL, rnode.minL + mid - l);
    newNode.minR = min(rnode.minR, lnode.minR + r - mid);
    return newNode;
}

void maintain(int o, int u) {
    int d = INF;
    if (color[u] == 1) d = 0;
    if(ch[u].size()) d = min(d, *(ch[u].begin()));
    segs[o].minL = segs[o].minR = d;
}

void buildTree(int o, int l, int r) {
    if (r - l == 1) {
        int u = idR[l];
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa[u] && bel[u] != bel[v]) {
                buildTree(root[v] = segCnt++, id[v], id[v] + sz[v]);
                ch[u].insert(segs[root[v]].minL + 1);
            }
            maintain(o, u);
        }
    }else {
        int mid = (l + r) / 2;
        buildTree(ls[o] = segCnt++, l, mid);
        buildTree(rs[o] = segCnt++, mid, r);
        segs[o] = merge(segs[ls[o]], segs[rs[o]], l, r);
    }
}

void process() {
    dfs1(0, -1);
    dfs2(0, 0);
    buildTree(root[0] = segCnt++, id[0], id[0] + sz[0]);
}

int query(int o, int l, int r, int target) {
    //cout << o << ' ' << l << ' ' << r << ' ' << target << endl;
    int ans = INF;
    if (r - l == 1) {
        int head = bel[target], fh = fa[head];
        ans = segs[o].minL; //到下面的链
        if (bel[target] != 0) {
            //到上面的链，由于是最小值，不用担心再次跑到本链！
            ans = min(ans,
            query(root[bel[fh]], id[bel[fh]], id[bel[fh]] + sz[bel[fh]], fh) + id[target] - id[head] + 1);
        }
    }else {
        int mid = (l + r) / 2;
        if (id[target] < mid) {
            ans = min(ans, segs[rs[o]].minL + mid - id[target]);
            ans = min(ans, query(ls[o], l, mid, target));
        }else {
            ans = min(ans, segs[ls[o]].minR + id[target] - mid + 1);
            ans = min(ans, query(rs[o], mid, r, target));
        }
    }
    return ans;
}

vector<int> path;
void findPath(int u) {
    while (u != -1) {
        path.push_back(u);
        u = fa[bel[u]];
    }
}

void modify(int o, int l, int r, int i) {
    if (r - l == 1) {
        int u = idR[l];
        if (i + 1 != (int)path.size()) {
            int nexT = bel[path[i + 1]];
            ch[u].erase(ch[u].find(segs[root[nexT]].minL + 1));
            modify(root[nexT], id[nexT], id[nexT] + sz[nexT], i + 1);
            ch[u].insert(segs[root[nexT]].minL + 1);
        }
        maintain(o, u);
    }else {
        int mid = (l + r) / 2;
        if (id[path[i]] < mid) modify(ls[o], l, mid, i);
        else modify(rs[o], mid, r, i);
        segs[o] = merge(segs[ls[o]], segs[rs[o]], l, r);
    }
}

int main() {
    //freopen("test.in", "r", stdin);
    blackCnt = n = ReadInt();
    memset(color, 0, sizeof(bool) * n);
    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();
    int q = ReadInt();
    while (q--) {
        int op = ReadInt();
        if (op == 0) {
            int u = ReadInt() - 1;
            if (color[u]) blackCnt++;
            else blackCnt--;
            color[u] = !color[u];
            path.clear();
            findPath(u);
            reverse(path.begin(), path.end());
            modify(root[0], id[0], id[0] + sz[0], 0);
        }else if(op == 1) {
            int u = ReadInt() - 1;
            if (blackCnt == n) puts("-1");
            else printf("%d\n", query(root[bel[u]], id[bel[u]], id[bel[u]] + sz[bel[u]], u));
        }else assert(false);
    }
    return 0;
}