Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * author: tourist
- * created: 07.02.2019 17:50:31
- **/
- #include <bits/stdc++.h>
- using namespace std;
- string to_string(string s) {
- return '"' + s + '"';
- }
- string to_string(const char* s) {
- return to_string((string) s);
- }
- string to_string(bool b) {
- return (b ? "true" : "false");
- }
- template <typename A, typename B>
- string to_string(pair<A, B> p) {
- return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
- }
- template <typename A>
- string to_string(A v) {
- bool first = true;
- string res = "{";
- for (const auto &x : v) {
- if (!first) {
- res += ", ";
- }
- first = false;
- res += to_string(x);
- }
- res += "}";
- return res;
- }
- void debug_out() { cerr << endl; }
- template <typename Head, typename... Tail>
- void debug_out(Head H, Tail... T) {
- cerr << " " << to_string(H);
- debug_out(T...);
- }
- #ifdef LOCAL
- #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
- #else
- #define debug(...) 42
- #endif
- class segtree {
- public:
- struct node {
- // don't forget to set default value (used for leaves)
- // not necessarily neutral element!
- long long mn = 0;
- long long add = 0;
- void apply(int l, int r, long long v) {
- mn += v;
- add += v;
- }
- };
- node unite(const node &a, const node &b) const {
- node res;
- res.mn = min(a.mn, b.mn);
- return res;
- }
- inline void push(int x, int l, int r) {
- int y = (l + r) >> 1;
- int z = x + ((y - l + 1) << 1);
- // push from x into (x + 1) and z
- if (tree[x].add != 0) {
- tree[x + 1].apply(l, y, tree[x].add);
- tree[z].apply(y + 1, r, tree[x].add);
- tree[x].add = 0;
- }
- }
- inline void pull(int x, int z) {
- tree[x] = unite(tree[x + 1], tree[z]);
- }
- int n;
- vector<node> tree;
- void build(int x, int l, int r) {
- if (l == r) {
- return;
- }
- int y = (l + r) >> 1;
- int z = x + ((y - l + 1) << 1);
- build(x + 1, l, y);
- build(z, y + 1, r);
- pull(x, z);
- }
- template <typename M>
- void build(int x, int l, int r, const vector<M> &v) {
- if (l == r) {
- tree[x].apply(l, r, v[l]);
- return;
- }
- int y = (l + r) >> 1;
- int z = x + ((y - l + 1) << 1);
- build(x + 1, l, y, v);
- build(z, y + 1, r, v);
- pull(x, z);
- }
- node get(int x, int l, int r, int ll, int rr) {
- if (ll <= l && r <= rr) {
- return tree[x];
- }
- int y = (l + r) >> 1;
- int z = x + ((y - l + 1) << 1);
- push(x, l, r);
- node res{};
- if (rr <= y) {
- res = get(x + 1, l, y, ll, rr);
- } else {
- if (ll > y) {
- res = get(z, y + 1, r, ll, rr);
- } else {
- res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
- }
- }
- pull(x, z);
- return res;
- }
- template <typename... M>
- void modify(int x, int l, int r, int ll, int rr, const M&... v) {
- if (ll <= l && r <= rr) {
- tree[x].apply(l, r, v...);
- return;
- }
- int y = (l + r) >> 1;
- int z = x + ((y - l + 1) << 1);
- push(x, l, r);
- if (ll <= y) {
- modify(x + 1, l, y, ll, rr, v...);
- }
- if (rr > y) {
- modify(z, y + 1, r, ll, rr, v...);
- }
- pull(x, z);
- }
- int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
- if (l == r) {
- return l;
- }
- push(x, l, r);
- int y = (l + r) >> 1;
- int z = x + ((y - l + 1) << 1);
- int res;
- if (f(tree[x + 1])) {
- res = find_first_knowingly(x + 1, l, y, f);
- } else {
- res = find_first_knowingly(z, y + 1, r, f);
- }
- pull(x, z);
- return res;
- }
- int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
- if (ll <= l && r <= rr) {
- if (!f(tree[x])) {
- return -1;
- }
- return find_first_knowingly(x, l, r, f);
- }
- push(x, l, r);
- int y = (l + r) >> 1;
- int z = x + ((y - l + 1) << 1);
- int res = -1;
- if (ll <= y) {
- res = find_first(x + 1, l, y, ll, rr, f);
- }
- if (rr > y && res == -1) {
- res = find_first(z, y + 1, r, ll, rr, f);
- }
- pull(x, z);
- return res;
- }
- int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
- if (l == r) {
- return l;
- }
- push(x, l, r);
- int y = (l + r) >> 1;
- int z = x + ((y - l + 1) << 1);
- int res;
- if (f(tree[z])) {
- res = find_last_knowingly(z, y + 1, r, f);
- } else {
- res = find_last_knowingly(x + 1, l, y, f);
- }
- pull(x, z);
- return res;
- }
- int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
- if (ll <= l && r <= rr) {
- if (!f(tree[x])) {
- return -1;
- }
- return find_last_knowingly(x, l, r, f);
- }
- push(x, l, r);
- int y = (l + r) >> 1;
- int z = x + ((y - l + 1) << 1);
- int res = -1;
- if (rr > y) {
- res = find_last(z, y + 1, r, ll, rr, f);
- }
- if (ll <= y && res == -1) {
- res = find_last(x + 1, l, y, ll, rr, f);
- }
- pull(x, z);
- return res;
- }
- segtree(int _n) : n(_n) {
- assert(n > 0);
- tree.resize(2 * n - 1);
- build(0, 0, n - 1);
- }
- template <typename M>
- segtree(const vector<M> &v) {
- n = v.size();
- assert(n > 0);
- tree.resize(2 * n - 1);
- build(0, 0, n - 1, v);
- }
- node get(int ll, int rr) {
- assert(0 <= ll && ll <= rr && rr <= n - 1);
- return get(0, 0, n - 1, ll, rr);
- }
- node get(int p) {
- assert(0 <= p && p <= n - 1);
- return get(0, 0, n - 1, p, p);
- }
- template <typename... M>
- void modify(int ll, int rr, const M&... v) {
- assert(0 <= ll && ll <= rr && rr <= n - 1);
- modify(0, 0, n - 1, ll, rr, v...);
- }
- // find_first and find_last call all FALSE elements
- // to the left (right) of the sought position exactly once
- int find_first(int ll, int rr, const function<bool(const node&)> &f) {
- assert(0 <= ll && ll <= rr && rr <= n - 1);
- return find_first(0, 0, n - 1, ll, rr, f);
- }
- int find_last(int ll, int rr, const function<bool(const node&)> &f) {
- assert(0 <= ll && ll <= rr && rr <= n - 1);
- return find_last(0, 0, n - 1, ll, rr, f);
- }
- };
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- int n, tt;
- cin >> n >> tt;
- vector<int> p(n);
- vector<int> w(n);
- for (int i = 1; i < n; i++) {
- cin >> p[i] >> w[i];
- p[i]--;
- }
- vector<vector<int>> qs(n);
- vector<int> L(tt), R(tt), v(tt);
- vector<long long> res(tt, -1);
- for (int i = 0; i < tt; i++) {
- cin >> v[i] >> L[i] >> R[i];
- v[i]--; L[i]--; R[i]--;
- qs[v[i]].push_back(i);
- }
- vector<long long> dst(n);
- for (int i = 1; i < n; i++) {
- dst[i] = dst[p[i]] + w[i];
- }
- vector<int> is_leaf(n, 1);
- for (int i = 1; i < n; i++) {
- is_leaf[p[i]] = 0;
- }
- const long long inf = (long long) 1e18;
- for (int i = 0; i < n; i++) {
- if (!is_leaf[i]) {
- dst[i] = inf;
- }
- }
- segtree st(dst);
- vector<int> stk;
- vector<int> to(n, n - 1);
- for (int i = 0; i < n; i++) {
- while (!stk.empty() && stk.back() != p[i]) {
- int u = stk.back();
- to[u] = i - 1;
- stk.pop_back();
- }
- stk.push_back(i);
- }
- debug(to);
- stk.clear();
- for (int i = 0; i < n; i++) {
- while (!stk.empty() && stk.back() != p[i]) {
- int u = stk.back();
- st.modify(0, n - 1, -w[u]);
- st.modify(u, to[u], 2 * w[u]);
- stk.pop_back();
- }
- stk.push_back(i);
- st.modify(0, n - 1, w[i]);
- st.modify(i, to[i], -2 * w[i]);
- for (int id : qs[i]) {
- res[id] = st.get(L[id], R[id]).mn;
- }
- }
- for (int i = 0; i < tt; i++) {
- cout << res[i] << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement