Pagini recente » Cod sursa (job #2684775) | Cod sursa (job #3176714) | Cod sursa (job #1401664) | Razvy | Cod sursa (job #3240131)
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
constexpr int nmax = 1e5 + 1;
constexpr int B = 300;
int lazy[400], unde[nmax], sub[nmax], d[nmax], e, val[nmax], s[nmax];
unordered_map<int,int> fr[400]; vector<int> g[nmax];
void build(int x, int t = 0)
{
sub[x] = -e; d[++e] = x; s[x] = e;
for(auto &it : g[x])
if(it != t) build(it, x);
sub[x] += e;
}
int main()
{
freopen("arbore.in", "r", stdin);
freopen("arbore.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
for(int i = B + 1; i < nmax ; i += B)
unde[i]++;
for(int i = 1; i < nmax ; i++)
unde[i] += unde[i-1];
int n, t, q, a, b; cin >> n >> q;
for(int i = 1; i < n ; i++)
{
cin >> a >> b; fr[unde[i]][0]++;
g[a].emplace_back(b),
g[b].emplace_back(a);
}
fr[unde[n]][0]++;
build(1); bool fun = false;
while(q--)
{
cin >> t >> a;
if(t == 2)
{
if(fun)
{
cout << "-1\n";
continue;
}
bool sem = 0;
for(int i = 0 ; i <= unde[n] && !sem ; i++)
{
if(!fr[i].count(a - lazy[i])) continue;
sem = 1; //cout << lazy[i] << '\n';
for(int j = i * B + 1; j <= min(n, (i + 1) * B); j++){
if(val[j] + lazy[i] == a)
{
//cout << val[j] << " " << lazy[i] << " " << a << '\n';
cout << s[j] << '\n';
break;
}}
}
if(!sem)
cout << "-1\n";
}
else
{
cin >> b; if(fun) continue;
int st = s[a]; int dr = st + sub[a] - 1;
for(int i = unde[st] + 1; i < unde[dr]; i++)
lazy[i] += b;
for(int i = st; unde[i] == unde[st] && i <= dr; i++)
fr[unde[st]][lazy[unde[st]] + val[i]]--,
fr[unde[st]][lazy[unde[st]] + val[i]+b]++, val[i] += b;
if(unde[st] != unde[dr])
for(int i = B * unde[dr] + 1; i <= dr; i++)
fr[unde[dr]][lazy[unde[dr]] + val[i]]--,
fr[unde[dr]][lazy[unde[dr]] + val[i]+b]++, val[i] += b;
}
}
}