Pagini recente » Cod sursa (job #1823775) | Cod sursa (job #2553058) | Cod sursa (job #2914776) | Cod sursa (job #1446606) | Cod sursa (job #2186597)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("arbore.in");
ofstream out("arbore.out");
const int Nmax = 100005;
vector<int> A[Nmax];
void DFS (int nod, vector<int>&Father)
{
for (auto i = 0; i < A[nod].size(); i++)
{
int nod_curent = A[nod][i];
if (Father[nod] == nod_curent) continue;
Father[nod_curent] = nod;
DFS(nod_curent, Father);
}
}
void parcurgere (int nod, int suma, int&rez, bool OK, vector<int> val, vector<int> bani, vector<int> Father)
{
if (OK == false)
for (auto i = 0; i < A[nod].size(); i++)
{
int nod_curent = A[nod][i];
if (Father[nod] == nod_curent) continue;
bani[nod_curent] = val[nod_curent] + bani[nod];
if (bani[nod_curent] == suma)
rez = nod_curent, OK = true;
parcurgere(nod_curent, suma, rez, OK, val, bani, Father);
}
}
int main()
{
int n, m;
in >> n >> m;
vector<int> val(n + 1), bani(n + 1), Father(n + 1);
for (int i = 1; i < n; i++)
{
int x, y;
in >> x >> y;
A[x].push_back(y);
A[y].push_back(x);
}
DFS(1, Father);
for (int i = 1; i <= m; i++)
{
int tip, p, s;
in >> tip;
if (tip == 1)
{
in >> p >> s;
val[p] = val[p] + s;
}
else
{
in >> s;
int rez;
bool OK = false;
bani[1] = val[1];
if (bani[1] == s)
out << 1 << '\n';
else
{
parcurgere(1, s, rez, OK, val, bani, Father);
out << rez << '\n';
}
}
}
return 0;
}