Областная олимпиада по информатике 2020 год, 9-11 классы

Задача E. Есмахан и стартап

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Есмахан - начал стартап по разведению моржов. Он нанял $n-1$ работника. Есмахан - сотрудник номер $1$, все остальные пронумерованы от $2$ до $n$. У каждого из работников есть один непосредственный начальник $p_i$. У Есмахан нет начальников. Гарантируется, что значения $p_i$ образуют дерево. Теперь Есмахан должен им заплатить. Работник с номером $i$ хочет получить $a_i$ тенге. Пусть $i$ работник получит $b_i$ тенге, тогда его недовольство будет $|a_i - b_i|$. У Есмахана есть принцип - каждый работник должен получить больше чем любой его подчиненный. Вам нужно распределить зарплаты так чтобы суммарное недовольство было минимально.

Формат входного файла

В первой строке одно целое число $n$ $(1 <= n <= 200000)$. Во второй строке $n - 1$ целых чисел $p_2, p_3, ... p_n$ $(1 <= p_i <= i - 1)$ - номера начальников работников. В третей строке $n$ целых чисел $a_1, a_2, ... a_n$ $(1 <= a_i <= 10^9)$ - ожидания работников.

Формат выходного файла

Выведите одно целое число - минимальное суммарное недовольство работников.

Система оценки

Данная задача содержит ровно $25$ тестов и каждый оценивается в $4$ баллов.

1. Тест из условия.
2. $1 <= n <= 1000$, $1 <= a_i <= 1000$ для $1 <= i <= n$, у каждого работника не больше одного подчиненного | 2 теста.
3. $1 <= n <= 1000$, $1 <= a_i <= 1000$ для $1 <= i <= n$ | 2 теста.
4. $1 <= n <= 1000$, у каждого работника не больше одного подчиненного | 2 теста.
5. $1 <= n <= 1000$ | 3 теста.
6. $1 <= n <= 200000$, у каждого работника не больше одного подчиненного | 5 тестов.
7. $1 <= n <= 200000$ | 10 тестов.

Пример:

Вход

7
1 2 1 1 5 6
1 2 3 1 4 3 3

Ответ

7

Замечание

Ответ в примере $b={5, 4, 3, 1, 4, 3, 2}$ ( Batyr Sardarbekov )

Комментарий/решение

показать/скрыть код

int n, a[N], mx[N], sz[N];
long long ans[N];
vector<int> g[N];
priority_queue<int> q[N];

void make(int v = 1) {
	sz[v] = 1;
	for (int to : g[v]) {
		make(to);
		sz[v] += sz[to];
		if (sz[mx[v]] < sz[to])
			mx[v] = to;
	}
}


void dfs(int v = 1, int d = 0) {
	a[v] += d;
	if (sz[v] == 1) {
		q[v].push(a[v]);
		return;
	}
	for (int to : g[v]) {
		dfs(to, d + 1);
		ans[v] += ans[to];
		if (mx[v] != to) {
			while (q[to].size()) {
				q[v].push(q[to].top());
				q[to].pop();
			}
		}
	}
	q[v].swap(q[mx[v]]);
	while (q[mx[v]].size()) {
		q[v].push(q[mx[v]].top());
		q[mx[v]].pop();
	}
	if (q[v].size() && a[v] < q[v].top())
		ans[v] += q[v].top() - a[v];
	q[v].push(a[v]);
	q[v].push(a[v]);
	q[v].pop();
}

int main() {
	speed;
	cin >> n;
	for (int i = 2, p; i <= n; ++i) {
		cin >> p;
		g[p].push_back(i);
	}
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	make();
	dfs();
	cout << ans[1] << '\n';
}

показать/скрыть код

from sys import setrecursionlimit

def make(n, p):
    global graph
    for i in range(n):
        s = set()
        for j in range(n-1):
            if i == p[j]-1:
                s.add(j+1)
        graph[i] = s


def dfs(graph, start, visited=None):
    global a
    if visited is None:
        visited = set()
    visited.add(start)
    for next in graph[start] - visited:
        if a[start] < a[next]:
            a[start] = a[next] + 1
            dfs(graph, 0, visited)
        elif a[start] == a[next]:
            a[next] -= 1
            dfs(graph, next, visited)
        else:
            dfs(graph, next, visited)
    return visited
               
graph = dict()

n = int(input())
p = list(map(int ,input().split()))
a = list(map(int, input().split()))
b = a.copy()
make(n, p)
dfs(graph, 0)

cnt = 0
for i in range(n):
    cnt += abs(a[i] -b[i])

print(cnt)

setrecursionlimit(10**9)

показать/скрыть код

#include <bits/stdc++.h>

//#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'
#define bit(x, i) ((x) >> (i) & 1)

using namespace std;
using ll = long long;
using pii = pair<int, int>
using vvt = vt< vt<int> >

const int N = 2e5 + 5, mod = 1e9 + 7, B = 500;
const ll inf = 1e18 + 7, LIM = (1ll << 60);
const double eps = 1e-6;

int n;
ll a[N], dp[N];
vt<int> g[N];
priority_queue<ll> q[N];

void dfs (int v, int p = -1, int dist = 1) {
	a[v] += dist;
	for (auto to: g[v]) {
		if (to != p) {
			dfs(to, v, dist + 1);
			dp[v] += dp[to];
			if (sz(q[to]) > sz(q[v])) q[v].swap(q[to]);
			while (!q[to].empty()) q[v].push(q[to].top()), q[to].pop();
		}
	}
	if (!q[v].empty() && a[v] < q[v].top()) dp[v] += q[v].top() - a[v];
	q[v].push(a[v]), q[v].push(a[v]);
	q[v].pop();
}

void solve () {
	cin >> n;
	for (int i = 2, p; i <= n; i++) cin >> p, g[p].pb(i), g[i].pb(p);
	for (int i = 1; i <= n; i++) cin >> a[i];
	dfs(1);
	cout << dp[1];	
	cout << '\n';
}

bool testcases = 0;

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	int test = 1;
	if (testcases) cin >> test;
	for (int cs = 1; cs <= test; cs++) {
		solve();
	}
}