Trồng Thuốc

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bạn đang chơi một trò chơi có $N$ phòng được nối với nhau bằng $N - 1$ hành lang, tạo thành một cây. Bạn cần hoàn thành các chuyến khám phá bắt đầu từ phòng $1$ để thăm tất cả các phòng ít nhất một lần.

Trước mỗi chuyến khám phá, một lọ thuốc xuất hiện tại một phòng cụ thể - bạn chỉ có thể thu thập nó nếu bạn đến phòng đó trong chuyến khám phá đó.

Lọ thuốc thứ $i$ xuất hiện tại phòng $p_{i}$ trước chuyến khám phá thứ $i$ . Hãy tìm số thuốc tối đa có thể thu thập trong khi hoàn thành bản đồ với số chuyến khám phá tối thiểu.

Dữ liệu vào

Dòng đầu tiên: số nguyên $N$ ( $2 \leq N \leq 10^{5}$ ).
Dòng thứ hai: $N$ số nguyên $p_{1}, p_{2}, \dots, p_{N}$ ( $1 \leq p_{i} \leq N$ ) - vị trí thuốc.
$N - 1$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $a$ và $b$ - một cạnh trong cây.

Dữ liệu ra

In một số nguyên duy nhất - số thuốc tối đa có thể thu thập.

Ràng buộc

$2 \leq N \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
5 5 4 3 2 1 1 2 1 3 3 4 3 5	2	Cần tối thiểu 3 chuyến. Chuyến 1: 1-3-5 (lấy thuốc ở 5). Chuyến 2: 1-3-4 (lấy thuốc ở 4). Chuyến 3: 1-2 (hoàn thành bản đồ).

Bình luận

Không có bình luận tại thời điểm này.