Pagini recente » Borderou de evaluare (job #3301350) | Cod sursa (job #3301449) | Cod sursa (job #463776) | Borderou de evaluare (job #1122321) | Cod sursa (job #3305701)
#include <fstream>
#include <vector>
#include <unordered_map>
using namespace std;
ifstream in("arbore.in");
ofstream out("arbore.out");
const int nmax = 1e5, valmax = 1e6, block = 325, nrblocks = nmax / block;
int n, nrq, value[nmax + 2], type, a, b;
int preorder[nmax + 2], leaffsub[nmax + 2];
int actually[nmax + 2];
vector <int> muchii[nmax + 2];
void dfs(int node, int father){
preorder[node] = (++preorder[0]);
actually[preorder[0]] = node;
leaffsub[node] = preorder[0];
for(auto nxt : muchii[node]){
if(nxt != father){
dfs(nxt, node);
leaffsub[node] = max(leaffsub[node], leaffsub[nxt]);
}
}
}
struct batog{
unordered_map <int, int> blocks[nrblocks + 2];
int marsblocks[nrblocks + 2], numberblocks;
int valuepreorder[nmax + 2];
int getblock(int x){ return x / block; }
int getleftt(int x){ return x * block; }
int getrightt(int x){ return (x + 1) * block - 1; }
void add(int pos, int value, int baseblk){
for(int blk = baseblk; blk <= numberblocks; blk++){
if(getleftt(blk) <= pos && pos <= getrightt(blk)){
for(int it = max(1, getleftt(blk)); it <= pos; it++){
blocks[blk][valuepreorder[it]]--;
if(blocks[blk][valuepreorder[it]] == 0)
blocks[blk].erase(valuepreorder[it]);
valuepreorder[it] += value;
blocks[blk][valuepreorder[it]]++;
}
return;
}else{ marsblocks[blk] += value; }
}
}
int query(int value){
for(int blk = 0; blk <= numberblocks; blk++){
if(blocks[blk].find(value - marsblocks[blk]) != blocks[blk].end()){
int lf = max(1, getleftt(blk));
int rg = min(n, getrightt(blk));
value -= marsblocks[blk];
for(int it = lf; it <= rg; it++){
if(valuepreorder[it] == value)
return actually[it];
}
}
}
return -1;
}
} sqrtdecomp;
int main(){
in>>n>>nrq;
for(int i = 1; i <= n - 1; i++){
in>>a>>b;
muchii[a].push_back(b);
muchii[b].push_back(a);
}
dfs(1, 0);
sqrtdecomp.numberblocks = (n / block + !!(n % block)) - 1;
for(int blk = 0; blk <= sqrtdecomp.numberblocks; blk++){
int lf = max(1, sqrtdecomp.getleftt(blk));
int rg = min(n, sqrtdecomp.getrightt(blk));
sqrtdecomp.blocks[blk][0] = rg - lf + 1;
}
for(int i = 1; i <= nrq; i++){
in>>type;
if(type == 1){
in>>a>>b;
sqrtdecomp.add(preorder[a] - 1, -b, sqrtdecomp.getblock(preorder[a] - 1));
sqrtdecomp.add(leaffsub[a], b, sqrtdecomp.getblock(preorder[a] - 1));
}else{
in>>a;
out<<sqrtdecomp.query(a)<<"\n";
}
}
return 0;
}