How to solve this question?

Правка en1, от hdude0164, 2022-04-24 14:30:43

You are given the hierarchy of a company, represented by a directed tree of N nodes  where N is the number of employees. Each employee has only one direct manager and possibly many indirect managers. Each employee can manage many employees directly and indirectly.

Each employee has a skill level A[x] and an expertise level.

The expertise level of an employee equals the count of employees y such that:

-> A[y] > A[x] -> The employee x manages the employee y (directly or indirectly).

A set of employees is a beautiful set if, none of the employees in the set manages the others directly or indirectly. The expertise of the set equals, the sum of the expertise levels for all the employees in the set.

Find the maximum expertise of a beautiful set with size at most K.

Notes: A tree is an undirected graph in which any two vertices are connected by exactly one path. A directed tree is a directed acyclic graph (DAG) whose underlying undirected graph is a tree.

The size of a set is the number of employees in the set.

Constraints: 1<=N<=10^5 1<=K<=100 1<=A[i]<=10^5 -1<=Parent[i]<=N

Input Format N K A[] Parent[]

Sample: Input 3 1 1 2 3 -1 1 2

Output 2

Input 3 1 1 1 3 -1 1 2

Output 1

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский hdude0164 2022-04-24 14:30:43 1297 Initial revision (published)