Cod sursa(job #910664)

Utilizator vendettaSalajan Razvan vendetta Data 10 martie 2013 22:21:43
Problema Arbore Scor 50
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

ifstream f("arbore.in");
ofstream g("arbore.out");

#define nmax 100005
#define ll long long

int n, m, sz, P[nmax], U[nmax], sum[nmax], sum2[nmax];
bool viz[nmax];
vector<int> gf[nmax];


void citeste(){
    f >> n >> m;
    int x, y;
    for(int i=1; i<n; ++i){
        f >> x >> y;
        gf[x].push_back(y);
        gf[y].push_back(x);
    }
}

void dfs(int nod){
    viz[nod] =1;
    P[nod] = ++sz;

    for(int i=0; i<gf[nod].size(); ++i){
        int vc = gf[nod][i];
        if (viz[vc] == 0){
            dfs(vc);
        }
    }
    U[nod] = sz;
}


void rezolva(){
    // o(1) pe uptadet si o(n) pe query cu smenul lui mars
    dfs(1);
    //for(int i=1; i<=n; ++i) cout << P[i] << " " << U[i] << "\n";

    int tip, p, s;
    for(int j=1; j<=m; ++j){
        f >> tip;
        if (tip == 1){
            f >> p >> s;
            sum[P[p]] += s;
            sum[U[p]+1] -= s;
        }else {
            f >> s;
            for(int i=1; i<=n; ++i) sum2[i] = sum2[i-1] + sum[i];
            int ok = 0;// pp ca nu e;
            for(int i=1; i<=n; ++i){
                if (sum2[ P[i] ] == s){
                    ok = 1;
                    g << i << "\n";
                    break;
                }
            }
            if (ok==0){
                g << -1 <<"\n";
            }
        }
    }
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}