Pagini recente » Cod sursa (job #298200) | Cod sursa (job #108219) | Cod sursa (job #2502365) | Cod sursa (job #2691249) | Cod sursa (job #1451135)
#include <bits/stdc++.h>
using namespace std;
#define wN second.first
#define wP second.second
#define wI first
ifstream fin("arbore.in");
ofstream fout("arbore.out");
const int SSIZE = 317 + 10;
const int NSIZE = 100000 + 10;
pair < int , int > p[NSIZE];
int add[SSIZE] , aux[NSIZE];
vector < pair < int , int > > iB[SSIZE];
int N , Q , x , y , type , i , crt , block;
vector < int > g[NSIZE];
int wB(int i)
{
return i / block;
}
int wiB(int i)
{
return i % block;
}
void df(int node,int fa)
{
p[node].first = ++crt;
aux[crt] = node;
for (int i=0;i<g[node].size();++i)
{
int to = g[node][i];
if (to != fa) df(to,node);
}
p[node].second = crt;
}
void build()
{
int i;
for (i = 0 ; i < N ; ++i)
iB[wB(i)].push_back({0 , i});
}
void update(int le,int ri,int x)
{
int crt , i , j1 , j2;
if (le % block != 0)
{
j1 = wB(le) + 1;
crt = wB(le);
for (i = 0 ; i < iB[crt].size() ; ++i)
if (le <= iB[crt][i].second && iB[crt][i].second <= ri)
iB[crt][i].first += x;
sort(iB[crt].begin(),iB[crt].end());
if (wB(le) == wB(ri)) return ;
} else j1 = wB(le);
if ((ri + 1) % block != 0)
{
j2 = wB(ri) - 1;
crt = wB(ri);
for (i = 0 ; i < iB[crt].size() ; ++i)
if (le <= iB[crt][i].second && iB[crt][i].second <= ri)
iB[crt][i].first += x;
sort(iB[crt].begin(),iB[crt].end());
if (wB(le) == wB(ri)) return ;
} else j2 = wB(ri);
for (i = j1 ; i <= j2 ; ++i)
add[i] += x;
}
int query(int x)
{
int ans = N , i , j1 , j2 , k , f;
for (i = 0 ; i <= wB(N - 1) ; ++i)
{
j1 = 0 , j2 = iB[i].size() - 1 , f = N;
while (j1 <= j2)
{
k = (j1 + j2) >> 1;
if (iB[i][k].first + add[i] == x)
{
f = min(f , iB[i][k].second);
j2 = k - 1;
}
if (iB[i][k].first + add[i] < x)
j1 = k + 1;
if (iB[i][k].first + add[i] > x)
j2 = k - 1;
}
ans = min(ans , f);
}
if (ans == N) return -1;
return aux[ans];
}
int main()
{
fin >> N >> Q;
block = (int)sqrt(1.0 * N);
for (i=1;i<N;++i)
{
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
crt = -1;
df(1,0);
build();
for (i=1;i<=Q;++i)
{
fin >> type;
if (type == 1)
{
fin >> x >> y;
update(p[x].first,p[x].second,y);
}
else
{
fin >> y;
fout << query(y) << '\n';
}
}
return 0;
}