Pagini recente » Cod sursa (job #3344959) | Cod sursa (job #589991) | Monitorul de evaluare | Cod sursa (job #3334724) | Cod sursa (job #3305693)
#include <fstream>
#include <vector>
#include <map>
using namespace std;
ifstream in("arbore.in");
ofstream out("arbore.out");
const int nmax = 1e5, valmax = 1e6, block = 400, 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{
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){
for(int blk = 0; blk <= numberblocks; blk++){
if(getleftt(blk) <= pos && pos <= getrightt(blk)){
for(int it = max(1, getleftt(blk)); it <= pos; it++)
valuepreorder[it] += value;
return;
}else{ marsblocks[blk] += value; }
}
}
int query(int value){
for(int i = 1; i <= n; i++){
if(valuepreorder[i] + marsblocks[getblock(i)] == value)
return actually[i];
};
/**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;
}
void debug(){
out<<"Debug: ";
for(int i = 1; i <= n; i++){
out<<valuepreorder[i] + marsblocks[getblock(i)]<<" ";
}; out<<"\n";
}
} 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);
}
for(int i = 1; i <= n; i++)
sqrtdecomp.blocks[0][0] = 1;
dfs(1, 0);
sqrtdecomp.numberblocks = (n / block + !!(n % block));
for(int i = 1; i <= nrq; i++){
in>>type;
if(type == 1){
in>>a>>b;
sqrtdecomp.add(preorder[a] - 1, -b);
sqrtdecomp.add(leaffsub[a], b);
}else{
in>>a;
out<<sqrtdecomp.query(a)<<"\n";
}
///sqrtdecomp.debug();
}
return 0;
}