Cod sursa(job #726813)
// http://infoarena.ro/problema/arbore
#include <fstream>
#include <vector>
using namespace std;
const int MAXSIZE = 100001;
ifstream in("arbore.in");
ofstream out("arbore.out");
int nodes,ops,sum;
bool gasit;
int money[MAXSIZE];
vector<int> graph[MAXSIZE];
void depthFirst(int node,int currentSum);
int main()
{
in >> nodes >> ops;
int from,to;
for(int i=1;i<nodes;i++)
{
in >> from >> to;
graph[from].push_back(to);
}
int type = 0,node = 0;
for(int i=1;i<=ops;i++)
{
in >> type;
if(type == 1)
{
in >> node >> sum;
money[node] += sum;
}
else
{
in >> sum;
/*bool found = false;
for(int k=1;k<=nodes;k++)
if(money[k] == sum)
{
out << k << "\n";
found = true;
break;
}*/
gasit = false;
depthFirst(1,money[1]);
if(!gasit)
out << "-1\n";
}
}
out.close();
return (0);
}
void depthFirst(int node,int currentSum)
{
if(gasit) return;
if(currentSum == sum || currentSum > sum)
{
out << node << "\n";
gasit = true;
return;
}
for(unsigned int i=0;i<graph[node].size();++i)
depthFirst(graph[node][i],currentSum + money[graph[node][i]]);
}