Untitled
unknown
plain_text
a year ago
4.1 kB
7
Indexable
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; #define fi first #define se second #define pp push_back #define all(x) (x).begin(), (x).end() #define Ones(n) __builtin_popcount(n) #define endl '\n' #define mem(arrr, xx) memset(arrr,xx,sizeof arrr) //#define int long long #define debug(x) cout << (#x) << " = " << x << endl void Gamal() { ios_base::sync_with_stdio(false); cin.tie(nullptr); #ifdef Clion freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout); #endif } int dx[] = {+0, +0, -1, +1, +1, +1, -1, -1}; int dy[] = {-1, +1, +0, +0, +1, -1, +1, -1}; const double EPS = 1e-9; const ll OO = 0X3F3F3F3F3F3F3F3F; const int N = 1e5 + 5, INF = INT_MAX, MOD = 1e9 + 7, LOG = 20; struct SEG { ll sum = 0; SEG() { } SEG(ll x) { sum = x; } }; struct segTree { vector<SEG> seg; int sz = 1, n; segTree(int nn) { n = nn; while (sz < nn) sz *= 2; seg.assign(2 * sz, SEG()); } SEG merge(SEG seg1, SEG seg2) { SEG ret; ret.sum = max(seg1.sum, seg2.sum); return ret; } void update(int i, ll val, int x, int lx, int rx) { if (lx == rx) { seg[x] = SEG(val); return; } int mid = (lx + rx) / 2, lf = 2 * x + 1, rt = 2 * x + 2; if (i <= mid) update(i, val, lf, lx, mid); else update(i, val, rt, mid + 1, rx); seg[x] = merge(seg[lf], seg[rt]); } void update(int i, ll val) { update(i, val, 0, 0, n - 1); } SEG query(int l, int r, int x, int lx, int rx) { if (l <= lx && r >= rx) return seg[x]; if (l > rx || r < lx) return {}; int mid = (lx + rx) / 2, lf = 2 * x + 1, rt = 2 * x + 2; return merge(query(l, r, lf, lx, mid), query(l, r, rt, mid + 1, rx)); } SEG query(int l, int r) { return query(l, r, 0, 0, n - 1); } }; vector<pii> adj[N]; vector<int> at[N]; ll sum[N]; int in[N], out[N], depth[N], timer; void dfs(int u, int p) { in[u] = timer++; at[depth[u]].push_back(u); for (auto &[v, w]: adj[u]) { if (v == p)continue; sum[v] = sum[u] + w; depth[v] = depth[u] + 1; dfs(v, u); } out[u] = timer - 1; } void solve() { int n; cin >> n; for (int i = 0; i < n - 1; ++i) { int u, v, w; cin >> u >> v >> w; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } int q; cin >> q; vector<pll> que(q); vector<int> L(q, 0), R(q, n - 1), ans(q, -1); for (int i = 0; i < q; ++i) { int u; cin >> u; ll p; cin >> p; que[i] = {u, p}; } dfs(1, 1); bool ok = true; while (ok) { vector<int> ev[n]; segTree seg(n); ok = false; for (int i = 0; i < q; ++i) { if (L[i] > R[i])continue; int mid = (L[i] + R[i]) / 2; ev[mid].push_back(i); ok = true; } for (int i = 0; i < n; ++i) { for (auto &u: at[i]) { seg.update(in[u], sum[u]); } for (auto &j: ev[i]) { ll val = seg.query(in[que[j].first], out[que[j].first]).sum - sum[que[j].first]; if (val >= que[j].second) { ans[j] = i; R[j] = i - 1; } else { L[j] = i + 1; } } } } for (int i = 0; i < q; ++i) { if (ans[i] == -1)cout << -1 << endl; else cout << ans[i] - depth[que[i].first] << endl; } } signed main() { Gamal(); int t = 1; // cin >> t; while (t--) { solve(); } }
Editor is loading...
Leave a Comment