Select Git revision
URI1135.cpp
-
Bruno Freitas Tissei authored
Signed-off-by:
Bruno Freitas Tissei <bft15@inf.ufpr.br>
Bruno Freitas Tissei authoredSigned-off-by:
Bruno Freitas Tissei <bft15@inf.ufpr.br>
URI1135.cpp 1.80 KiB
#include <bits/stdc++.h>
#define MAX 101010
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define MAXLOG 20
#define fi first
#define se second
#define sz size()
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
vector<ii> graph[MAX];
ll h[MAX];
ll par[MAX][MAXLOG], cost[MAX][MAXLOG];
void dfs(int v, int p = -1, ll c = 0) {
par[v][0] = p;
cost[v][0] = c;
if (p + 1)
h[v] = h[p] + 1;
for (int i = 1; i < MAXLOG; ++i)
if (par[v][i - 1] + 1) {
par[v][i] = par[par[v][i - 1]][i - 1];
cost[v][i] += cost[v][i - 1] + cost[par[v][i - 1]][i - 1];
}
for (auto u : graph[v])
if (p != u.fi)
dfs(u.fi, v, u.se);
}
void preprocess(int v) {
memset(par, -1, sizeof par);
memset(cost, 0, sizeof cost);
dfs(v);
}
ll query(int p, int q) {
ll ans = 0;
if (h[p] < h[q])
swap(p, q);
for (int i = MAXLOG - 1; i >= 0; --i)
if (par[p][i] + 1 && h[par[p][i]] >= h[q]) {
ans += cost[p][i];
p = par[p][i];
}
if (p == q)
return ans;
for (int i = MAXLOG - 1; i >= 0; --i)
if (par[p][i] + 1 && par[p][i] != par[q][i]) {
ans += cost[p][i] + cost[q][i];
p = par[p][i];
q = par[q][i];
}
if (p == q) return ans;
else return ans + cost[p][0] + cost[q][0];
}
int main() {
ll li;
int ai, n;
int q, s, t;
while (scanf("%d", &n) && n) {
for (int i = 0; i < n + 1; ++i)
graph[i].clear();
for (int i = 1; i <= n - 1; ++i) {
scanf("%d %lld", &ai, &li);
graph[ai].pb(ii(i, li));
}
preprocess(0);
scanf("%d", &q);
for (int i = 0; i < q; ++i) {
scanf("%d %d", &s, &t);
if (i) printf(" ");
printf("%lld", query(s, t));
}
printf("\n");
}
return 0;
}