Sengxian's Blog

//  Created by Sengxian on 3/16/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//    Spoj QTREE III
#include <algorithm>
#include <iostream>
#include <cassert>
#include <climits>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#define lowbit(x) x & (-x)
using namespace std;
inline int ReadInt() {
    int n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 1) + (n << 3) + ch - '0', ch = getchar();
    return n;
}

struct FenwickTree {
    static const int maxNode = 100000 + 3;
    int a[maxNode], n;
    void init(int _n) {n = _n; memset(a, 0, sizeof a);}
    inline void add(int x, int v) {
        x++;
        while (x <= n) a[x] += v, x += lowbit(x);
    }
    inline int sum(int x) {
        x++;
        int val = 0;
        while (x > 0) val += a[x], x -= lowbit(x);
        return val;
    }
    //[l, r)
    inline int Sum(int l, int r) {
        return sum(r - 1) - sum(l - 1);
    }
}Fen;


const int maxn = 100000 + 3;
vector<int> G[maxn];
int n, q, fa[maxn], dep[maxn], s[maxn], timestamp = 0;
int id[maxn], idR[maxn], bel[maxn];

void init() {
    for (int i = 0; i < n; ++i) G[i].clear();
    fa[0] = -1, timestamp = 0;
    Fen.init(n);
}

int dfs1(int u, int f) {
    fa[u] = f, dep[u] = f == -1 ? 0 : dep[f] + 1;
    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;
    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);
    }
}

vector<int> allPath;
int query(int a) {
    allPath.clear();
    allPath.push_back(a);
    while (bel[a] != 0) allPath.push_back(a = fa[bel[a]]);
    if(a != 0) allPath.push_back(0);
    reverse(allPath.begin(), allPath.end());
    //for (int i = 0; i < allPath.size(); ++i) cout << allPath[i] + 1 << ' ';
    //cout << endl;
    for (int i = 0; i < (int)allPath.size() - 1; ++i) {
        int f = allPath[i], t = allPath[i + 1];
        if (bel[f] != bel[t]) {
            if (Fen.Sum(id[f], id[f] + 1) == 1) return f + 1;
            f = bel[t];
        }
        int l = id[f], r = id[t] + 1;
        if (Fen.Sum(l, r) == 0) continue;
        else {
            while(r - l > 1) {
                int mid = (l + r) / 2;
                if (Fen.Sum(l, mid) > 0) r = mid;
                else l = mid;
            }
            return idR[l] + 1;
        }
    }
    return -1;
}

int main() {
    //freopen("test.in", "r", stdin);
    int caseNum = 1;
    while (caseNum--) {
        int q;
        n = ReadInt(), q = ReadInt();
        init();
        int f, t;
        for (int i = 0; i < n - 1; ++i) {
            f = ReadInt() - 1, t = ReadInt() - 1;
            G[f].push_back(t);
            G[t].push_back(f);
        }
        dfs1(0, -1);
        dfs2(0, 0);
        while (q--) {
            int op = ReadInt();
            if (op == 0) {
                int v = ReadInt() - 1, val = Fen.Sum(id[v], id[v] + 1);
                if(val == 0) val = 1; else val = -1;
                Fen.add(id[v], val);
            }else if (op == 1) {
                printf("%d\n", query(ReadInt() - 1));
            }else assert(false);
        }
    }
    return 0;
}