Cod sursa(job #1321549)

Utilizator retrogradLucian Bicsi retrograd Data 19 ianuarie 2015 11:49:15
Problema Arbore Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<fstream>
#include<vector>

#define MAXN 100001

using namespace std;
typedef int var;

ifstream fin("arbore.in");
ofstream fout("arbore.out");

vector<var> G[MAXN];
vector<var> FII[MAXN];
bool VIZ[MAXN];
var SUM[MAXN];
var n, m;

void dfs(var node) {
    VIZ[node] = 1;
    for(; !G[node].empty(); G[node].pop_back()) {
        if(!VIZ[G[node].back()]) {
            FII[node].push_back(G[node].back());
            dfs(G[node].back());
        }
    }
}

void read() {
    fin>>n>>m;
    var a, b;
    for(var i=1; i<n; i++) {
        fin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1);
}

var solve(var node, var s) {
    if (s == SUM[node]) return node;
    if (s < SUM[node]) return -1;
    var t= 0;
    for(vector<var>::iterator it = FII[node].begin(); it != FII[node].end(); ++it) {
        t = solve(*it, s - SUM[node]);
        if(t != -1) {
            return t;
        }
    }
    return -1;
}


int main() {
    read();
    var type, t, s;
    while(m--) {
        fin>>type;
        if(type == 1) {
            fin>>t>>s;
            SUM[t] += s;
        }
        else {
            fin>>s;
            fout<<solve(1, s)<<'\n';
        }
    }
    return 0;
}