Pagini recente » Unlucky... | Cod sursa (job #37713) | Cod sursa (job #3290394) | Rating Vlad Isoc (badboyvlad) | Cod sursa (job #96)
Cod sursa(job #96)
#include <cstdio>
#include <cmath>
#include <bitset>
#include <vector>
using namespace std;
const int MAXN = 100005;
const int MAXS = 1000001;
const int MAXsqrtN = 350;
int N, M, sqrtN;
vector<int> con[MAXN];
int df[MAXN], l[MAXN], r[MAXN], df0;
int groff[MAXsqrtN], gr0, grl[MAXsqrtN], grr[MAXsqrtN], gr[MAXN], s[MAXN];
bitset<MAXS> grpos[MAXsqrtN];
int u[MAXN];
void dfs(int k)
{
vector<int> :: iterator it;
if (u[k]) return;
u[k] = 1;
df[df0] = k;
l[k] = df0++;
for (it = con[k].begin(); it != con[k].end(); it++)
dfs(*it);
r[k] = df0 - 1;
}
void update(int gr, int l, int r, int S)
{
int i;
for (i = grl[gr]; i <= grr[gr]; i++)
grpos[gr][ s[i] ] = 0;
for (i = l; i <= r; i++)
s[i] += S;
for (i = grl[gr]; i <= grr[gr]; i++)
grpos[gr][ s[i] ] = 1;
}
int main()
{
freopen("arbore.in", "rt", stdin);
freopen("arbore.out", "wt", stdout);
int i, j, k;
for (scanf("%d %d", &N, &M), sqrtN = (int)sqrt((double)N), i = 1; i < N; i++)
scanf("%d %d", &j, &k),
con[j].push_back(k),
con[k].push_back(j);
for (i = 1, gr0 = 0; i <= N; i++)
{
if (i % sqrtN == 1) { gr0++; grpos[gr0][0] = 1; grl[gr0] = i; grr[gr0 - 1] = i - 1; }
gr[i] = gr0;
}
grr[gr0] = N;
int S;
for (dfs(df0 = 1); M; M--)
{
scanf("%d", &k);
if (k == 1)
{
scanf("%d %d", &i, &S);
j = r[i]; i = l[i];
if (gr[i] == gr[j])
update(gr[i], i, j, S);
else
{
update(gr[i], i, grr[ gr[i] ], S);
for (k = gr[i] + 1; k < gr[j]; k++)
groff[k] += S;
update(gr[j], grl[ gr[j] ], j, S);
}
}
else
{
scanf("%d", &S);
for (i = 1; i <= gr0; i++)
if (S >= groff[i] && grpos[i][S - groff[i]])
break;
if (i == gr0 + 1) { printf("-1\n"); continue; }
S -= groff[i];
for (j = grl[i]; j <= grr[i]; j++)
if (s[j] == S)
{
printf("%d\n", df[j]);
break;
}
}
}
return 0;
}