Pagini recente » Cod sursa (job #1454763) | Cod sursa (job #1562591) | Cod sursa (job #447230) | Cod sursa (job #2031215) | Cod sursa (job #1223020)
#include <iostream>
#include <vector>
#include <fstream>
#include <set>
#include <unordered_map>
#include <map>
#include <bitset>
using namespace std;
const int NMAX = 100002;
ifstream ff("arbore.in");
ofstream g("arbore.out");
vector<int> gf[NMAX];
int f[NMAX], l[NMAX], seq[NMAX], length = 0, value[NMAX], add[NMAX];
vector< pair<int,int> > bucket;
multiset<int> mySet[318];
//map<int,int>myMap[318];
bool myMap[318][1000001];
int used[NMAX];
int n, m, sqrtN;
bitset<1000001> viz[318];
void dfs(int node){
used[node] = 1;
f[node] = ++length;
seq[length] = node;
for(int i=0; i<gf[node].size(); ++i){
if (used[gf[node][i]] == 0){
dfs(gf[node][i]);
}
}
l[node] = length;
}
int main() {
//freopen("arbore.in", "r", stdin);
//freopen("arbore.out", "w", stdout);
ff >> n >> m;
for(int i=1; i<n; ++i){
int x, y;
ff >> x >> y;
gf[x].push_back(y);
gf[y].push_back(x);
}
dfs(1);
sqrtN = 1;
//n = 100000;
for(; sqrtN*sqrtN <= n; ++sqrtN);
for(int i=1, j=1; i<=n; i+=sqrtN, ++j){
bucket.push_back( make_pair(i, min(n,i+sqrtN-1) ) );
// cout << j << " " << i << " " << min(n, i+sqrtN-1) << "\n";
}
for(int i=0; i<bucket.size(); ++i){
viz[i][0] = 1;
}
for(; m; --m){
int tip;
ff >> tip;
if (tip == 1){
int s, p;
ff >> p >> s;
for(int i=0; i<(int)bucket.size(); ++i){
if ( bucket[i].first > l[p] || bucket[i].second < f[p] ) continue;
if ( bucket[i].first >= f[p] && bucket[i].second <= l[p] ){
add[i] += s;
continue;
}
for(int j=max(bucket[i].first, f[p]); j<=min(bucket[i].second, l[p]); ++j){
//mySet[i].erase(mySet[i].find( value[seq[j]] ));
//myMap[i][ value[seq[j]] ]--;
viz[i][ value[seq[j]] ] = 0;
value[seq[j]] += s;
//myMap[i][ value[seq[j]] ]++;
//mySet[i].insert( value[seq[j]] );
}/*
for(int j=bucket[i].first; j<=bucket[i].second; ++j){
viz[i][ value[seq[j]] ] = 1;
}*/
}
}else{
int s;
ff >> s;
bool gasit = false;
for(int i=0; i<(int)bucket.size(); ++i){
//multiset<int>::iterator it = mySet[i].find(s-add[i]);
//if (it == mySet[i].end()) continue;
if (s-add[i] < 0 || viz[i][s-add[i]] == 0) continue;
gasit = true;
for(int j=bucket[i].first; j<=bucket[i].second; ++j){
if (value[ seq[j] ] + add[i] == s){
g << seq[j] << "\n";
break;
}
}
break;
}
if (!gasit) g << -1 << "\n";
}
}
return 0;
}