Mai intai trebuie sa te autentifici.
Cod sursa(job #2224876)
Utilizator | Data | 25 iulie 2018 14:04:36 | |
---|---|---|---|
Problema | Arbore | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.04 kb |
// stiu ca nu intra in timp ca parcurg la query uri tot arborele ca sa afisez (-1)
// da is curios sa vad cat ia
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;
ifstream f ("arbore.in");
ofstream g ("arbore.out");
const int NMAX = 1e5 + 5;
int v[NMAX], leftEnd[NMAX], rightEnd[NMAX];
int n, m, ind;
vi adj[NMAX];
struct Node {
int sumMax, sum, lazy;
Node () {
sumMax = sum = lazy = 0;
}
} segmTree[4 * NMAX];
void dfs (int node, int dad) {
v[ind++] = node;
leftEnd[node] = ind;
for (auto &i : adj[node]) {
if (i != dad)
dfs (i, node);
}
rightEnd[node] = ind;
}
void update (int node, int left, int right, int x, int y, int val) {
if (x <= left && right <= y) {
segmTree[node].lazy += val;
segmTree[node].sum += val;
segmTree[node].sumMax += val;
return;
}
int mid = left + (right - left) / 2;
if (x <= mid) {
update (2 * node + 1, left, mid, x, y, val);
}
if (y > mid) {
update (2 * node + 2, mid + 1, right, x, y, val);
}
segmTree[node].sumMax = max (segmTree[2 * node + 1].sumMax, segmTree[2 * node + 2].sumMax);
}
void propagate (int node, int left, int right) {
if (!segmTree[node].lazy) return;
if (left != right) {
segmTree[2 * node + 1].lazy += segmTree[node].lazy;
segmTree[2 * node + 1].sum += segmTree[node].lazy;
segmTree[2 * node + 1].sumMax += segmTree[node].lazy;
segmTree[2 * node + 2].lazy += segmTree[node].lazy;
segmTree[2 * node + 2].sum += segmTree[node].lazy;
segmTree[2 * node + 2].sumMax += segmTree[node].lazy;
}
segmTree[node].lazy = 0;
}
int query (int node, int left, int right, int val) {
if (segmTree[node].sum == val) return v[left];
propagate(node, left, right);
if (left == right) {
return ((segmTree[node].sum == val) ? v[left] : (-1));
}
int mid = left + (right - left) / 2;
int ret = -1;
if (segmTree[2 * node + 1].sumMax >= val) {
ret = query (2 * node + 1, left, mid, val);
}
if (ret != -1) return ret;
if (segmTree[2 * node + 2].sumMax >= val) {
ret = query (2 * node + 2, mid + 1, right, val);
}
return ret;
}
int main() {
f >> n >> m;
for (int i = 0; i < n - 1; ++i) {
int u, v;
f >> u >> v;
--u; --v;
adj[u].pb (v);
adj[v].pb (u);
}
dfs (0, -1);
while (m--) {
int type, node, sum;
f >> type;
if (type - 1) {
f >> sum;
g << query (0, 0, n - 1, sum) << '\n';
} else {
f >> node >> sum;
--node;
update (0, 0, n - 1, leftEnd[node], rightEnd[node], sum);
}
}
f.close();
g.close();
return 0;
}