1801E - Gasoline prices - CodeForces Solution

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int maxn = 2e5 + 10;
const ll mod = 1e9 + 7;

ll power(ll base, ll st)
{
    ll ans = 1;
    while(st > 0)
    {
        if (st % 2 == 1)
            ans = (ans * base) % mod;
        st /= 2;
        base = (base * base) % mod;
    }
    return ans;
}

struct query
{
    int a, b, c, d;
} ask[maxn];

int n, p[maxn], q;
ll l[maxn], r[maxn];
vector < int > child[maxn];

void input()
{
    cin >> n;
    for (int i = 2; i <= n; i ++)
        cin >> p[i];
    for (int i = 1; i <= n; i ++)
        cin >> l[i] >> r[i];
    cin >> q;
    for (int i = 1; i <= q; i ++)
        cin >> ask[i].a >> ask[i].b >> ask[i].c >> ask[i].d;
}


void build_graph()
{
    for (int i = 2; i <= n; i ++)
    {
        child[p[i]].push_back(i);
    }
}

const int maxlog = 21;

int jump[maxlog][maxn], depth[maxn], in[maxn], out[maxn], timer;
void dfs(int v)
{
    in[v] = ++ timer;
    jump[0][v] = p[v];
    for (int j = 1; jump[j - 1][v] != 0; j ++)
        jump[j][v] = jump[j - 1][jump[j - 1][v]];

    for (int u : child[v])
    {
        depth[u] = depth[v] + 1;
        dfs(u);
    }
    out[v] = timer;
}

struct edge
{
    int v, u, w;

    edge(int _v, int _u, int _w)
    {
        v = _v;
        u = _u;
        w = _w;
    }
};

vector < edge > edges[maxlog];
int lg[maxn];

int get_jump(int v, int k)
{
    for (int bit = 0; bit < maxlog; bit ++)
        if ((k & (1 << bit)))
            v = jump[bit][v];
    return v;
}

int get_lca(int v, int u)
{
    if (depth[v] > depth[u])
        swap(v, u);
    u = get_jump(u, depth[u] - depth[v]);
    for (int bit = maxlog - 1; bit >= 0; bit --)
    {
        if (jump[bit][v] != jump[bit][u])
        {
            v = jump[bit][v];
            u = jump[bit][u];
        }
    }
    if (v == u)
        return v;

    return jump[0][v];
}

int cur_edge;
void sparse_split(int a, int b, int c, int d)
{
    if (depth[a] > depth[b])
    {
        swap(a, b);
        swap(c, d);
    }

    int len = depth[b] - depth[a] + 1;
    int lg_len = lg[depth[b] - depth[a] + 1] - 1;

    if (depth[c] <= depth[d])
    {
        edges[lg_len].push_back(edge(get_jump(b, len - (1 << lg_len)), get_jump(d, len - (1 << lg_len)), cur_edge));
        edges[lg_len].push_back(edge(b, d, cur_edge));
    }
    else
    {
        edges[lg_len].push_back(edge(get_jump(b, len - (1 << lg_len)), c + n, cur_edge));
        edges[lg_len].push_back(edge(b, get_jump(c, len - (1 << lg_len)) + n, cur_edge));
    }

}

vector < edge > price_edges[maxn];

int lead[maxn * 2];

int find_leader(int v)
{
    return (lead[v] == v) ? v : (lead[v] = find_leader(lead[v]));
}

bool unite(int v, int u)
{
    v = find_leader(v);
    u = find_leader(u);
    if (v == u)
        return false;

    if (rand() % 2)
        swap(v, u);
    lead[u] = v;
    return true;
}

void push_edge(edge cur, int layer)
{
    int mid1 = jump[layer - 1][cur.v];
    int mid2 = 0;

    //cout << cur.v << " -- " << cur.u << " -- " << layer << endl;
    //cout << mid1 << endl;
    if (cur.u <= n)
    {
        mid2 = jump[layer - 1][cur.u];
        edges[layer - 1].push_back(cur);
        edges[layer - 1].push_back(edge(mid1, mid2, cur.w));
    }
    else
    {
        mid2 = jump[layer - 1][cur.u - n];
        edges[layer - 1].push_back(edge(cur.v, mid2 + n, cur.w));
        edges[layer - 1].push_back(edge(mid1, cur.u, cur.w));
    }
}

void solve_layer(int layer)
{
    for (edge cur : edges[layer])
    {
        price_edges[cur.w].push_back(cur);
    }

    for (int i = 1; i <= 2 * n; i ++)
    {
        lead[i] = i;
    }

    for (int price = 1; price <= q; price ++)
    {
        for (edge cur : price_edges[price])
        {
            if (unite(cur.v, cur.u))
            {
                push_edge(cur, layer);
            }
        }
        price_edges[price].clear();
    }
}

ll ans;

void unite_final(int v, int u)
{
    v = find_leader(v);
    u = find_leader(u);
    if (v == u)
        return;

    if (rand() % 2)
        swap(v, u);
    lead[u] = v;

    if (l[u] <= r[u])
        ans = (ans * power(r[u] - l[u] + 1, mod - 2)) % mod;

    if (l[v] <= r[v])
        ans = (ans * power(r[v] - l[v] + 1, mod - 2)) % mod;

    l[v] = max(l[v], l[u]);
    r[v] = min(r[v], r[u]);

    if (l[v] <= r[v])
        ans = (ans * (r[v] - l[v] + 1)) % mod;
    else
        ans = 0;
}

void solve_last_layer()
{

    for (edge cur : edges[0])
    {
        if (cur.u > n)
            cur.u -= n;
        price_edges[cur.w].push_back(cur);
    }

    for (int i = 1; i <= 2 * n; i ++)
    {
        lead[i] = i;
    }

    ans = 1;
    for (int i = 1; i <= n; i ++)
        ans = (ans * (r[i] - l[i] + 1)) % mod;

    for (int price = 1; price <= q; price ++)
    {
        for (edge cur : price_edges[price])
        {
            unite_final(cur.v, cur.u);
            ///cout << cur.v << " " << cur.u << " " << cur.w << endl;
        }
        cout << ans << endl;
    }
}
void split_edge(int a, int b, int c, int d)
{
    if (depth[a] > depth[b])
    {
        swap(a, b);
        swap(c, d);
    }

    if (in[a] <= in[b] && out[b] <= out[a])
    {
        if ((in[c] <= in[d] && out[d] <= out[c]) ||
                (in[d] <= in[c] && out[c] <= out[d]))
        {
            sparse_split(a, b, c, d);
            return;
        }

        int lca = get_lca(c, d);
        int len_left = depth[c] - depth[lca] + 1;
        int len_right = depth[d] - depth[lca];
        int mid_vertex = get_jump(b, len_right - 1);
        int start_vertex = get_jump(d, len_right - 1);
        split_edge(a, p[mid_vertex], c, lca);
        split_edge(mid_vertex, b, start_vertex, d);
        return;
    }

    int left_lca = get_lca(a, b);
    int right_lca = get_lca(c, d);

    int left_len = depth[a] - depth[left_lca] + 1;
    int right_len = depth[b] - depth[left_lca];


    if (left_len < depth[c] - depth[right_lca] + 1)
    {
        int ver = get_jump(c, left_len - 1);
        split_edge(a, left_lca, c, ver);
        split_edge(get_jump(b, right_len - 1), b, p[ver], d);
    }
    else if (left_len == depth[c] - depth[right_lca] + 1)
    {
        split_edge(a, left_lca, c, right_lca);
        split_edge(get_jump(b, right_len - 1), b, get_jump(d, right_len - 1), d);
    }
    else
    {
        int ver = get_jump(d, right_len - 1);
        split_edge(a, left_lca, c, p[ver]);
        split_edge(get_jump(b, right_len - 1), b, ver, d);
    }

}

void split_edges()
{
    for (int i = 1; i <= n; i ++)
        lg[i] = lg[i / 2] + 1;
    for (int i = 1; i <= q; i ++)
    {
        cur_edge = i;
        split_edge(ask[i].a, ask[i].b, ask[i].c, ask[i].d);
    }

    /**for (int st = 0; st < 3; st ++)
    {
    cout << "power " << st << " " << edges[st].size() << endl;
    for (edge cur : edges[st])
    {
        cout << cur.v << " " << cur.u << " " << cur.w << endl;
    }
    cout << "--------------" << endl;
    }*/
}


void solve_layers()
{
    for (int layer = maxlog - 1; layer > 0; layer --)
        solve_layer(layer);

    solve_last_layer();
}

void solve()
{
    input();
    build_graph();
    dfs(1);
    split_edges();
    solve_layers();
}
int main()
{
    speed();
    solve();
    return 0;
}
/**
5
1 1 2 2
2 4
1 3
1 3
2 4
4 4
1
3 4 5 3
*/