Can anyone explain "small-large" merging or any other technique for this problem ?

Правка en1, от Roronoa__Zoro, 2024-08-03 17:03:32

You are given a tree consisting of N nodes. You are also given two arrays A and P of size N each, where the value A[i] denotes the value written on the i th node and the value P[i] denotes that there is an edge between the node i and P[i]. We say that an edge is considered good, if after deleting this edge (this will result in formation of 2 trees), the values in each of the nodes of the trees are distinct . Find the total number of good edges present in tree.

Constraints.

$$$1 \le N \le 10^{5}$$$

$$$1 \le A[i] \le 10^{5}$$$

$$$1 \le P[i] \le 10^{5}$$$

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Roronoa__Zoro 2024-08-03 17:03:32 654 Initial revision (published)