Balancing Tree USACO

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <chrono>
#include <cassert>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <random>

#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#  define __builtin_popcountll __popcnt64
#endif

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define x first
#define y second
#define ld long double
#define ll long long
#define ull unsigned long long
#define us unsigned short
#define lsb(x) ((x) & (-(x)))
#define pii pair <int, int>

using namespace std;

const int MOD = 998244353;

int lgput(int n, int p, int mod = MOD) {
    int ans = 1, x = n;

    while (p) {
        if (p & 1)
            ans = 1LL * ans * x % mod;
        x = 1LL * x * x % mod;
        p >>= 1;
    }

    return ans;
}

int T, b;

int n, x;
int sol;

pair <ll, ll> v[100005], seg[100005];
vector <int> g[100005];
ll ans[100005], mx[100005];

void dfs(int nod, int d) {

    ll mx = max(0LL, v[nod].x - d), mn = min((ll)1e9, v[nod].y + d);

    for (auto& fiu : g[nod]) {
        dfs(fiu, d);

        mx = max(mx, seg[fiu].x);
        mn = min(mn, seg[fiu].y);
    }

    seg[nod] = { mx, mn };

    //cout << nod << " : " << mx << ", " << mn << "\n";
}

void dfs2(int nod, int tata = 0) {
    ans[nod] = max(v[nod].x, seg[nod].x);
    ans[nod] = max(ans[nod], mx[tata]);
    mx[nod] = max(mx[tata], ans[nod] - sol);

    for (auto& fiu : g[nod]) {
        dfs2(fiu, nod);
    }

    //cout << nod << " : " << mx << ", " << mn << "\n";
}

pii dfs3(int nod) {
    int mn = (int)1e9, mx = 0;

    for (auto& fiu : g[nod]) {
        pii x = dfs3(fiu);

        mn = min(mn, x.x);
        mx = max(mx, x.y);
    }

    assert(ans[nod] - mn <= sol && mx - ans[nod] <= sol);

    return { mn, mx };
}

bool check(int val) {
    dfs(1, val);

    for (int i = 1; i <= n; i++) {
        if (seg[i].x > seg[i].y || seg[i].y < v[i].x || v[i].y < seg[i].x)
            return 0;
    }

    return 1;
}

void solve(int t) {
    cin >> n;

    for (int i = 1; i <= n; i++)
        g[i].clear(), mx[i] = 0;

    for (int i = 1; i < n; i++) {
        cin >> x;
        g[x].push_back(i + 1);
    }

    for (int i = 1; i <= n; i++) {
        cin >> v[i].x >> v[i].y;
    }

    int st = 0, dr = (int)1e9, mid;

    while (st <= dr) {
        mid = (st + dr) >> 1;

        if (check(mid))
            dr = mid - 1;
        else
            st = mid + 1;
    }

    sol = st;

    cout << sol << "\n";

    if (b == 1) {
        check(sol);

        dfs2(1);
        for (int i = 1; i <= n; i++)
            cout << ans[i] << " ";
        cout << "\n";

        dfs3(1);
    }
}

int main() {
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    srand(time(0));

    int T = 1;

    cin >> T >> b;

    for (int t = 1; t <= T; t++) {
        solve(t);
    }

    return 0;
}