Pagini recente » Cod sursa (job #395953) | Cod sursa (job #522077) | Cod sursa (job #292224) | Cod sursa (job #750131) | Cod sursa (job #1223025)
#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];
int unde[NMAX];
const int Cifmax = (1<<14);
int poz;
char S[Cifmax];
void next(){
++poz; if (poz == Cifmax){
fread(S, 1, Cifmax, stdin); poz = 0;
}
}
void buf(int &nr){
nr = 0;
for(; S[poz]<'0' || S[poz]>'9'; next());
for(; S[poz]>='0' && S[poz]<='9'; ){
nr = nr * 10 + (S[poz] - '0');
next();
}
}
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;
buf(n); buf(m);
for(int i=1; i<n; ++i){
int x, y;
// ff >> x >> y;
buf(x); buf(y);
gf[x].push_back(y);
gf[y].push_back(x);
}
dfs(1);
sqrtN = 1;
//n = 100000;
for(; sqrtN*sqrtN <= n; ++sqrtN);
--sqrtN;
for(int i=1, j=1; i<=n; i+=sqrtN, ++j){
bucket.push_back( make_pair(i, min(n,i+sqrtN-1) ) );
for(int j=i; j<=i+sqrtN-1; ++j) unde[j] = (int)bucket.size()-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;
buf(tip);
if (tip == 1){
int s, p;
//ff >> p >> s;
buf(p); buf(s);
for(int i=unde[f[p]]; i<=unde[l[p]]; ++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;
buf(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;
}