Pagini recente » Cod sursa (job #571848) | Cod sursa (job #764579) | Cod sursa (job #1054967) | Cod sursa (job #201734) | Cod sursa (job #1321549)
#include<fstream>
#include<vector>
#define MAXN 100001
using namespace std;
typedef int var;
ifstream fin("arbore.in");
ofstream fout("arbore.out");
vector<var> G[MAXN];
vector<var> FII[MAXN];
bool VIZ[MAXN];
var SUM[MAXN];
var n, m;
void dfs(var node) {
VIZ[node] = 1;
for(; !G[node].empty(); G[node].pop_back()) {
if(!VIZ[G[node].back()]) {
FII[node].push_back(G[node].back());
dfs(G[node].back());
}
}
}
void read() {
fin>>n>>m;
var a, b;
for(var i=1; i<n; i++) {
fin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
dfs(1);
}
var solve(var node, var s) {
if (s == SUM[node]) return node;
if (s < SUM[node]) return -1;
var t= 0;
for(vector<var>::iterator it = FII[node].begin(); it != FII[node].end(); ++it) {
t = solve(*it, s - SUM[node]);
if(t != -1) {
return t;
}
}
return -1;
}
int main() {
read();
var type, t, s;
while(m--) {
fin>>type;
if(type == 1) {
fin>>t>>s;
SUM[t] += s;
}
else {
fin>>s;
fout<<solve(1, s)<<'\n';
}
}
return 0;
}