Untitled
unknown
plain_text
2 months ago
4.5 kB
3
Indexable
#include <iostream> #include <stdio.h> #include <fstream> #include <time.h> #include <algorithm> #include <vector> #include <queue> #include <string.h> #include <assert.h> #include <map> #include <math.h> #include <functional> #include <set> #include <unordered_map> #include <numeric> #include <cstdlib> #include <iomanip> #include <bitset> #include <complex> #include <list> #include <stack> #include <deque> #include <chrono> #include <unordered_set> using namespace std; #define Chris "test" #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define FORD(i, a, b) for(int i = (a); i <= (b); ++i) #define REP(i, a, b) for(int i = (a); i > (b); --i) #define REPD(i, a, b) for(int i = (a); i >= (b); --i) #define FORE(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++) #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() #define MARK(i) (1LL << (i)) #define bit(x, i) (((x) >> (i)) & 1) #define pb push_back #define pf push_front #define pob pop_back #define pof pop_front #define emp emplace_back #define fi first #define se second #define MIN(x,y) if (x > (y)) x = (y) #define MAX(x,y) if (x < (y)) x = (y) #define mp make_pair #define mem(v, a) memset((v), (a), sizeof((v))) #define MINE(v) *min_element(All(v)) #define MAXE(v) *max_element(All(v)) #define el "\n" #define mu2(a) (1 << ((a))) #define bitcount(a) __builtin_popcountll(a) #define Chris_ signed main() #define faster ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define showTime() cerr << '\n' << "Running time: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n"; #define file(Chris) if(fopen(Chris".inp", "r")){freopen(Chris".inp", "r", stdin);freopen(Chris".out", "w", stdout);} typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef vector<int> vii; typedef vector<ll> vll; typedef set<int> sii; typedef map<int, int> mii; typedef stack<int> sti; typedef deque<int> dqi; typedef queue<int> quei; typedef unordered_map<int, int> umii; typedef unordered_set<int, int> umsii; const ll mod = 1e9 + 7; const int inf = (int) 100005; const int LOG = (int) 17; const int base = (int) 131; const ll m2 = 1LL * mod * mod; #define cong(a, b, m) ((((a) % (m)) + ((b) % (m))) % (m)) #define tru(a, b, m) ((((a) % (m)) - ((b) % (m))) % (m)) #define nhan(a, b, m) ((((a) % (m)) * ((b) % (m))) % (m)) #define chia(a, b, m) ((((a) % (m)) * ((pow(b, -1) % (m))) % (m)) const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; int root, n, q, u, v, a, l; vii g[inf]; int parent[inf], depth[inf], up[inf][LOG]; ll dist[inf]; void dfs(int u, int p, int d) { parent[u] = p; depth[u] = d; for(int v : g[u]) { if(v == p) continue; dfs(v, u, d + 1); } } void binary_lifting() { FORD(u, 1, n) up[u][0] = parent[u]; FOR(i, 1, LOG) { FORD(u, 1, n) { up[u][i] = up[up[u][i - 1]][i - 1]; } } } // tìm tổ tiên thứ k của nút u int ancestor_k(int u, int k) { for(int i = 0; mu2(i) <= k; ++i) { if(bit(k, i)) { u = up[u][i]; } } return u; } // tìm nút cha chung gần nhất của u và v int lca(int u, int v) { if(depth[u] < depth[v]) { swap(u, v); } u = ancestor_k(u, depth[u] - depth[v]); if(u == v) return u; REPD(i, LOG - 1, 0) { if(up[u][i] != up[v][i]) { u = up[u][i]; v = up[v][i]; } } return parent[u]; } void nhap() { while(cin >> n && n) { parent[0] = 0; depth[0] = 0; dist[0] = 0; FOR(i, 1, n) { cin >> a >> l; parent[i] = a; depth[i] = depth[a] + 1; dist[i] = dist[a] + l; } binary_lifting(); cin >> q; FOR(i, 0, q) { cin >> u >> v; int x = lca(u, v); ll ans = dist[v] + dist[u] - 2LL * dist[x]; cout << ans; if(i < q - 1) { cout << " "; } } cout << el; } } void solve() { nhap(); } Chris_ { faster file(Chris) solve(); showTime(); return 0; }
Editor is loading...
Leave a Comment