Pagini recente » Cod sursa (job #683341) | Cod sursa (job #531341) | Cod sursa (job #2950361) | Cod sursa (job #63448) | Cod sursa (job #726790)
Cod sursa(job #726790)
// 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);
void depthFirst2(int node);
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;
depthFirst(node);
}
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;
depthFirst2(1);
if(!gasit)
out << "-1\n";
}
}
out.close();
return (0);
}
void depthFirst(int node)
{
money[node] += sum;
for(unsigned int i=0;i<graph[node].size();++i)
depthFirst(graph[node][i]);
}
void depthFirst2(int node) {
if(gasit || money[node] > sum) return;
if(money[node] == sum) {
out << node << "\n", gasit = true;
return;
}
for(int i=0;i<graph[node].size();i++)
depthFirst2(graph[node][i]);
}