Pagini recente » Cod sursa (job #258272) | Cod sursa (job #863662) | Cod sursa (job #270905) | Cod sursa (job #2764575) | Cod sursa (job #1393515)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ofstream out ("arbore.out");
const int MAXN = 100000 + 10;
vector <int> Graf[MAXN];
int N, M;
int now;
int H[2 * MAXN];
int First[MAXN], Last[MAXN];
bool Viz[MAXN];
int Sum[MAXN * 4], Max[MAXN * 4];
void DFS (int nod)
{
now ++;
H[now] = nod;
First[nod] = now;
Viz[nod] = 1;
vector <int> :: iterator it;
for (it = Graf[nod].begin (); it != Graf[nod].end (); ++ it)
if (!Viz[*it]){
DFS (*it);
++ now;
H[now] = nod;
}
Last[nod] = now;
}
void update (int nod, int st, int dr, int a, int b, int val)
{
if (a <= st && dr <= b){
Sum[nod] += val;
Max[nod] = Sum[nod] + max (Max[2 * nod], Max[2 * nod + 1]);
return;
}
int mid = (st + dr) / 2;
if (a <= mid)
update (nod * 2, st, mid, a, b, val);
if (mid < b)
update (nod * 2 + 1, mid + 1, dr, a, b, val);
Max[nod] = Sum[nod] + max (Max[2 * nod], Max[2 * nod + 1]);
}
int found;
void query (int nod, int st, int dr, int val)
{
if (found != -1)
return;
if (Sum[nod] == val){
found = H[st];
return;
}
if (st < dr && Sum[nod] < val && Max[nod] >= val){
int mid = (st + dr) / 2;
query (nod * 2, st, mid, val - Sum[nod]);
query (nod * 2 + 1, mid + 1, dr, val - Sum[nod]);
}
}
class Reader
{
private:
ifstream in;
static const int BUFF_SIZE = (1 << 12);
char S[BUFF_SIZE];
int now;
public:
Reader (const string &file_name)
{
in.open (file_name.c_str ());
in.read (S, BUFF_SIZE);
now = 0;
}
void getBlock ()
{
in.read (S, BUFF_SIZE);
now = 0;
}
char getChar ()
{
if (now == BUFF_SIZE)
getBlock ();
return S[now ++];
}
int getInt ()
{
int ret = 0;
char c;
do{
c = getChar ();
} while (!isdigit (c));
do{
ret = ret * 10 + c - '0';
c = getChar ();
}while (isdigit (c));
return ret;
}
Reader& operator >> (int &X)
{
X = getInt ();
return (*this);
}
};
Reader in ("arbore.in");
int main()
{
int i, a, b;
int op;
in >> N >> M;
for (i = 1; i < N; i ++){
in >> a >> b;
Graf[a].push_back (b);
Graf[b].push_back (a);
}
DFS (1);
for (i = 1; i <= M; i ++){
in >> op;
if (op == 1){
in >> a >> b;
update (1, 1, now, First[a], Last[a], b);
}
else{
in >> a;
found = -1;
query (1, 1, now, a);
out << found << "\n";
}
}
return 0;
}