Untitled

 avatar
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