Pagini recente » Cod sursa (job #2508089) | Cod sursa (job #2871239) | Cod sursa (job #2692663) | Cod sursa (job #881455) | Cod sursa (job #2152296)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#define maxn 100005
using namespace std;
int N, M;
vector <int> G [maxn];
int S [maxn];
int precalc [maxn];
bool vizitat [maxn];
int befeu(int s)
{
memset(vizitat, 0, sizeof(vizitat));
memset(precalc, 0, sizeof(precalc));
queue <int> Q;
int sum = 0;
//cout<<Q.size()<<"\n";
Q.push(1);
vizitat[1] = 1;
precalc[1] = S[1];
while(!Q.empty())
{
int cur = Q.front();
//cout<<"Nod curent: "<<cur<<"\n";
Q.pop();
//cout<<"Suma curenta: "<<precalc[cur]<<"\n";
if(precalc[cur] == s)
return cur;
for (int i = 0; i < G[cur].size(); ++i)
if(!vizitat[G[cur][i]])
{
Q.push(G[cur][i]);
vizitat[G[cur][i]] = 1;
precalc[G[cur][i]] = precalc[cur] + S[G[cur][i]];
}
}
return -1;
}
int main()
{
ifstream in ("arbore.in");
ofstream out ("arbore.out");
in>>N>>M;
for(int i = 1; i < N; ++i)
{
int x, y;
in>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i = 0; i < M; ++i)
{
int t, p, s;
in>>t;
if(t == 1)
{
in>>p>>s;
S[p] += s;
}
else
{
in>>s;
out<<befeu(s)<<"\n";
}
}
return 0;
}