Cod sursa(job #1263818)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 15 noiembrie 2014 10:44:19
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
/// Craciun Catalin
///  Arbore
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

#define NMax 100005

using namespace std;

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

long long n,m;
long long P[NMax];
long long sume[NMax];

void firstOp(long long sef, long long suma) {
    sume[sef] += suma;
}

long long sumFor(long long x) {

    long long sum = 0;

    int pos;
    for (pos = x; P[pos] != pos; pos = P[pos]) {
        sum+=sume[pos];
    }
    sum+=sume[pos];

    sume[x] = sum - sume[pos];
    P[x] = pos;

    return sum;
}

long long secondOp(long long suma) {

    for (long long i=1;i<=n;i++)
        if (sumFor(i) == suma)
            return i;

    return -1;
}

void read() {

    f>>n>>m;
    for (long long i=1;i<=n;i++)
        P[i] = i;

    for (long long i=1;i<n;i++) {
        long long x, y;
        f>>x>>y;
        if (x > y) {
            long long aux = x;
            x = y;
            y = aux;
        }

        P[y] = x;
    }

    for (long long j=1;j<=m;j++) {
        long long type;
        f>>type;
        if (type == 1) {
            long long sef, suma;
            f>>sef>>suma;
            firstOp(sef, suma);
        } else if (type == 2) {
            long long suma;
            f>>suma;
            g<<secondOp(suma)<<'\n';
        }
    }

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

int main() {

    memset(sume, 0, sizeof(sume));
    read();

    return 0;
}