Задача такая. Дан граф из n вершин и затем дано l[i], r[i]. Для каждого вершины можно выбрать число из отрезка l[i] <= x <= r[i]. Теперь допустим y это максимальная разница между такими числами, что одно число будет числом предка, а второе число будет сына. То есть y = max(allofthe(i, j) where i прямой предок j). Нужно найти минимальное y
Мое решение таково. Давайте бинарить ответ и будем делать для каждого поддерева считать возможный отрезок чисел. И когда мы в какой то вершине допустим ответ для сына это lv[i], rv[i]. То сделаем сканлайн и сперва добавим lv[i] - x(число которое бинарим) и rv[i] + x и потом добавим еще l[i], r[i]. И если будет такая точка что там пересекаются все сыновья + 1, то тогда эта точка может быть нашим ответом. И так строится ответ для текущей вершины.
Вот мой код
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
const ll maxn = 1e6 + 1, maxm = 1e5 + 1;
const ll mod = 998244353, inf = 1e9;
int t, b;
int n;
int p[maxn], s[maxn], q[maxn];
ll lv[maxn], rv[maxn], is = 0;
vector<int> g[maxn];
void dfs(int v, int y){
if (is)
return;
for (auto to : g[v]){
dfs(to, y);
}
vector<pair<ll, int>> sc;
for (auto to : g[v]){
sc.pb(mp(lv[to] - y, 0));
sc.pb(mp(rv[to] + y, 1));
}
sc.pb(mp(s[v], 0));
sc.pb(mp(q[v], 1));
sort(sc.begin(), sc.end());
int curr = 0;
lv[v] = 1e9 + 1;
rv[v] = -1;
for (auto it : sc){
pair<ll, int> cur = it;
if (cur.s == 0){
curr += 1;
if (curr == (int)g[v].size() + 1){
lv[v] = min(lv[v], cur.f);
rv[v] = max(rv[v], cur.f);
}
}
else{
if (curr == (int)g[v].size() + 1){
rv[v] = max(rv[v], cur.f);
lv[v] = min(lv[v], cur.f);
}
curr -= 1;
}
}
if (lv[v] > rv[v])
is = 1;
}
bool check(int x){
is = 0;
dfs(1, x);
return (!is);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> t >> b;
while (t--){
cin >> n;
for (int i = 2; i <= n; ++i){
cin >> p[i];
g[p[i]].pb(i);
}
for (int i = 1; i <= n; ++i){
cin >> s[i] >> q[i];
}
int l = 0, r = 1e9, ans = - 1;
while (l <= r){
int mid = (l + r) / 2;
if (check(mid)){
r = mid - 1, ans = mid;
}
else{
l = mid + 1;
}
}
cout << ans << '\n';
for (int i = 1; i <= n; ++i){
g[i].clear();
}
}
}
Есть ли решение лучше и мое решение вообще рабочее?
