Pagini recente » Cod sursa (job #59239) | Cod sursa (job #2028327) | Cod sursa (job #548503) | Cod sursa (job #1903622) | Cod sursa (job #3231845)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("arbore.in");
ofstream g ("arbore.out");
const int nmax = 1e5 + 1, sqmax = 317;
vector<int> L[nmax], lin; // L vectorul de muchii si lin = arborele liniarizat
int subarb[nmax]; // nr de descendenti ai lui nod
int poz[nmax], sum[nmax]; // pozitia nodului in liniarizare si suma sa
int st[sqmax], dr[sqmax], sumbuc[sqmax], maxibuc[sqmax]; // retin capetele stanga si dreapta & suma si maximul pe fiecare bucata
int i = 1;
void dfs (int node, int father){
subarb[node] += 1;
lin.push_back(node);
poz[node] = i++;
for (auto son : L[node]){
if (son != father)
dfs(son, node);
}
subarb[father] += subarb[node];
}
int main()
{
int n, m;
f >> n >> m; // n = 73 => sq = 8 => siz = 10 (avem nevoie de fix 10 bucati, deci crestem siz)
int sq = sqrt(n); // n = 80 => sq = 8 => siz = 11 (nu mai crestem siz, tot 10 bucati avem nevoie)
int siz = n / sq + 1;
if (n % sq != 0) siz++;
//cout << n << " " << sq << " " << siz << "\n\n";
st[1] = 1;
dr[1] = sq;
for (int i = 2; i < siz; ++i){
st[i] = st[i - 1] + sq;
dr[i] = dr[i - 1] + sq;
}
dr[siz - 1] = min(dr[siz - 1], n); // reparam capatul dreapta al ultimii bucati
for (int i = 1; i < n; ++i){
int x, y;
f >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
dfs(1,0);
for (int i = 1; i <= n; ++i) subarb[i]--; // scadem 1 pentru ca am numarat si nodul in sine
//for (auto i : lin) cout << i << " ";
//cout << "\n";
//for (int i = 1; i <= n; ++i) cout << subarb[i] << " ";
//for (int i = 1; i < siz; ++i)
//cout << st[i] << " " << dr[i] << " " << i << "\n";
int fr[siz][nmax]; // de cate ori apare in bucata i valoarea j
for (int i = 1; i < siz; ++i)
fr[i][0] = dr[i] - st[i] + 1; // initial, valoarea 0 apare de st - dr + 1 ori (lungimea)
while (m--){
int q;
f >> q;
if (q == 1){
int root, val;
f >> root >> val;
int x = poz[root], y = x + subarb[root]; // intervalul [x, y]
//cout << x << " " << y << " ";
int stbuc = (x / sq);
if (x % sq != 0) stbuc ++; // daca x NU este capat de dreapta al unei bucati, adaugam 1
int drbuc = (y / sq);
if (y % sq != 0) drbuc ++; // daca y NU este capat de dreapta al unei bucati, adaugam 1
//cout << stbuc << " " << drbuc << "\n"; // intervalul atinge bucatile de la stbuc la drbuc
//cout << stbuc << " " << drbuc << "\n";
if (drbuc == stbuc){
for (int i = x; i <= y; ++i){
fr[drbuc][sum[i]]--; // scadem frecventa la fosta valoare
sum[i] += val; // crestem valoarea
fr[drbuc][sum[i]]++; // crestem frecventa la valoarea noua
}
}
else if (drbuc - stbuc == 1){
for (int i = x; i <= dr[stbuc]; ++i){
fr[stbuc][sum[i]]--;
sum[i] += val;
fr[stbuc][sum[i]]++;
}
for (int i = y; i >= st[drbuc]; --i){
fr[drbuc][sum[i]]--; // scadem frecventa la fosta valoare
sum[i] += val; // crestem valoarea
fr[drbuc][sum[i]]++; // crestem frecventa la valoarea noua
}
}
else {
for (int i = x; i <= dr[stbuc]; ++i){ // elementele singuratice din stanga
//fr[stbuc][sum[i]]--;
sum[i] += val;
//fr[stbuc][sum[i]]++;
maxibuc[stbuc] = max(maxibuc[stbuc], sum[i] + sumbuc[stbuc]);
}
for (int i = y; i >= st[drbuc]; --i){ // elementele singuratice din dreapta
//fr[drbuc][sum[i]]--;
sum[i] += val;
//fr[drbuc][sum[i]]++;
maxibuc[drbuc] = max(maxibuc[drbuc], sum[i] + sumbuc[drbuc]);
}
for (int i = stbuc + 1; i < drbuc; ++i){ // actualizam suma pe bucatile complete
sumbuc[i] += val;
maxibuc[i] += val;
}
}
//for (int i = 1; i <= siz; ++i) cout << sumbuc[i] << " ";
}
else {
int s, ans = -1; // suma cautata
f >> s;
//cout << m;
for (int i = 1; i < siz; ++i){ // pt fiecare bucata
if (fr[i][s - sumbuc[i]] > 0){ // daca avem solutie in bucata
//cout << i;
for (int sol = st[i]; sol <= dr[i]; ++sol){ // cautam in bucata
if (sum[sol] == s - sumbuc[i]){ // valoarea s - sumbuc[i]
ans = poz[sol];
}
continue;
}
continue;
}
continue;
}
g << ans << "\n";
}
}
return 0;
}