Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

SPOJQTREE 3

Solução: Patrícia Hongo

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>

using namespace std;

#define MAXN 100023
#define ii pair<int, int>

vector<int> t[MAXN];

/* Obtem o RMQ em [a,b]; chamar com root=0, rl=0, rr=n-1 */
int query(int root, int rl, int rr, int a, int b, int ch) {
    if (a > b) return -1;

    if (rl==a && rr==b) return t[ch][root];
    int rm = (rl+rr)/2;

    int p1 = query(2*root+1, rl, rm, a, min(b, rm), ch);
    int p2 = query(2*root+2, rm+1, rr, max(a, rm+1), b, ch);
    if(p1 == -1 && p2 == -1) return -1;
    else if(p1 == -1) return p2;
    else if(p2 == -1) return p1;
    return p2;
}
/* Muda posiao x para vx; chamar com root=0, rl=0, rr=n-1 */
void update(int root, int rl, int rr, int x, int vx, int a, int ch) {
    if (rl==rr){
    if(vx==1)
        t[ch][root] = a;
    else
        t[ch][root] = -1;
    }
    else {
    int rm = (rl+rr)/2;
    if (x <= rm) update(2*root+1, rl, rm, x, vx, a, ch);
    else update(2*root+2, rm+1, rr, x, vx, a, ch);
    int p1 = t[ch][2*root+1];
    int p2 = t[ch][2*root+2];
    if(p1 == -1 && p2 == -1) t[ch][root] = -1;
    else if(p1 == -1) t[ch][root] = p2;
    else if(p2 == -1) t[ch][root] = p1;
    else t[ch][root] = p2;
    //t[ch][root] = max(t[ch][2*root+1], t[ch][2*root+2]);
    }
}

vector<int> g[MAXN];
/* Vertice do topo da chain i, tam da chain i e qtd delas */
int head[MAXN], chsz[MAXN], nch;
/* Chain do vErtice i e seu Indice nela (cresce pra raiz) */
int chain[MAXN], chidx[MAXN];
/* Altura do vertice i, seu antecessor e tam da suBarvore */
int depth[MAXN], pai[MAXN], size[MAXN];

/* Adiciona um vertice v no topo da chain c */
void chadd(int v, int c) {
    chidx[v] = chsz[c]++;
    chain[v] = c;
    head[c] = v;
}

/* Gera as chains e vetores associados */
void dfshl(int x) {
    size[x]=1;
    for (int i = 0; i < g[x].size(); i++) {
    int v = g[x][i];
    if (pai[x] != v) {
        depth[v] = depth[x]+1;
        pai[v] = x;
        dfshl(v);
        size[x] += size[v];
    }
    }

    chain[x] = -1;
    for (int i = 0; i < g[x].size(); i++)
    if (g[x][i] != pai[x] && size[g[x][i]] > size[x]/2)
        chadd(x, chain[g[x][i]]);
    if (chain[x] == -1) chadd(x, nch++);
}


int val[MAXN];
int chtr[MAXN], ntr = 0;

/* Exemplo de LCA. Percorre as chains no caminho entre a e b
   Pode ser alterado para responder query usando uma estrutura
   de dados de intervalos por chain (por ex. BIT, segtree) */

int LCA(int a, int b) {
    int mm = 0x3f3f3f3f;
    if(val[a] == 1) mm = a;
    if(val[b] == 1) return 0;

    while (chain[a] != chain[b]) {

    if (depth[head[chain[a]]] > depth[head[chain[b]]]){
        // query chain[a] em [chidx[a], chsz[chain[a]]-1]
        int x = query(0, 0, chsz[chain[a]]-1,
              chidx[a], chsz[chain[a]]-1, chtr[chain[a]]);

        if(x != -1)
        mm = x;

        a = pai[head[chain[a]]];
        if(val[a] == 1)
        mm = a;
    }
    }
    if (depth[a] < depth[b]) {
    // query chain[a] em [chidx[b], chidx[a]]
    int x = query(0, 0, chsz[chain[a]]-1,
              chidx[b], chidx[a], chtr[chain[a]]);
    if(x != -1) mm = x;
    return mm;
    }
    // query chain[a] em [chidx[a], chidx[b]]
    int x = query(0, 0, chsz[chain[a]]-1,
          chidx[a], chidx[b], chtr[chain[a]]);
    if(x != -1) mm=x;

    return mm;
 }





int n, q;

int main(){
    int a, b, c;

    scanf("%d %d", &n, &q);
    nch=0;
    memset(chsz,0,sizeof(chsz));
    memset(val, 0, sizeof(val));
    for (int i=0; i<n; i++)
    g[i].clear();
    for(int i = 0; i < n-1; ++i){
    scanf("%d %d",&a,&b);
    --a; --b;
    g[a].push_back(b);
    g[b].push_back(a);
    }
    dfshl(0);

    for(int i = 0; i< nch; ++i){
    chtr[i] = ntr;
    t[ntr++].assign(4*(chsz[i]+2), -1);
    }

    while(q--){
    scanf("%d %d", &c, &a);
    --a;
    if(c == 0){
        val[a] = 1-val[a];
        update(0, 0, chsz[chain[a]]-1, chidx[a], val[a], a, chtr[chain[a]]);
        continue;
    }
    int rt = LCA(a, 0);
    if(rt < 0x3f3f3f3f-5)
        printf("%d\n", rt+1);
    else printf("-1\n");
    }

    return 0;
}