Pagini recente » Cod sursa (job #2137912) | Cod sursa (job #2199200) | Cod sursa (job #2396578)
/// 10;30
#include <fstream>
#include <vector>
#include <bitset>
#include <cmath>
#define DIMN 200010
#define DIM 1000002
#define DIM_BUCKET 500
using namespace std;
ifstream in ("arbore.in");
ofstream out ("arbore.out");
vector <int> L[DIMN];
bitset <DIM> f[DIM_BUCKET];
int add[DIMN],a[DIMN],viz[DIMN],v[DIMN],st[DIM_BUCKET],dr[DIM_BUCKET],nrb[DIMN];
int n,m,c,p,s,i,bucket,start,fin,k,lg,x,y,ok;
pair <int,int> poz[DIMN];
void dfs (int nod){
viz[nod] = 1;
v[++k] = nod;
poz[nod].first = k;
for (int i=0;i<L[nod].size();i++){
int vecin = L[nod][i];
if (!viz[vecin])
dfs (vecin);
}
v[++k] = nod;
poz[nod].second = k;
}
/*void get_poz (int p){
if (poz[p].first % lg != 0)
start = (poz[p].first/lg)+1;
else start = poz[p].first/lg;
if (poz[p].second % lg != 0)
fin = (poz[p].second/lg)-1;
else fin = poz[p].second/lg;
}*/
int main (){
in>>n>>m;
for (i=1;i<n;i++){
in>>x>>y;
L[x].push_back (y);
L[y].push_back (x);
}
dfs (1);
lg = (int)sqrt(k);
for (i=1;i<=k;i++){
nrb[i] = i/lg; /// in ce bucket se afla un element
if (i%lg != 0)
nrb[i]++;
}
for (i=1;i<=k/lg;i++){
st[i] = (i-1)*lg+1; /// unde incepe si unde se termina un bucket
dr[i] = min(i*lg,k);
}
for (;m--;){
in>>c;
if (c == 1){
in>>p>>s;
x = poz[p].first, y = poz[p].second;
if (nrb[x] == nrb[y]){ /// intervalul meu e tot inclus intr un bucket
for (i=x;i<=y;i++)
a[i] += s;
for (i=st[nrb[x]];i<=dr[nrb[x]];i++)
f[nrb[x]][i] = 0;
for (i=st[nrb[x]];i<=dr[nrb[x]];i++)
f[nrb[x]][a[i]] = 1;
} else {
for (bucket=nrb[x]+1;bucket<nrb[y];bucket++)
add[bucket] += s; /// lazy ul
//add[nrb[x]] = add[nrb[y]] = 0;
for (i=st[nrb[x]];i<=dr[nrb[x]];i++)
f[nrb[x]][i] = 0; /// mai intai le demarchez pe toate din intervalul bucketului din stanga
for (i=x;i<=dr[nrb[x]];i++)
a[i] += s;
for (i=st[nrb[x]];i<=dr[nrb[x]];i++)
f[nrb[x]][a[i]] = 1;
/// acum fac acelasi lucru si pentru dreapta
for (i=st[nrb[y]];i<=dr[nrb[y]];i++)
f[nrb[y]][i] = 0;
for (i=st[nrb[y]];i<=y;i++)
a[i] += s;
for (i=st[nrb[y]];i<=dr[nrb[y]];i++)
f[nrb[y]][a[i]] = 1;
}
} else {
in>>s;
for (bucket=1;bucket<=n/lg;bucket++){
ok = 0;
if (s-add[bucket] >= 0 && f[bucket][s-add[bucket]]){
for (i=st[bucket];i<=dr[bucket];i++)
if (a[i] == s-add[bucket]){
out<<v[i]<<"\n";
ok = 1;
break;
}
}
if (ok) break;
}
if (!ok)
out<<"-1\n";
}
}
return 0;
}