Đồng Bộ Tín Hiệu · canuc80k7913

Một mạng hình cây có gốc $1$ . Các đỉnh $1, \dots, N$ là nút nối, còn $N + 1, \dots, N + M$ là các đầu nhận. Mỗi cạnh có độ dài dương ban đầu; tín hiệu đi trên mọi cạnh với cùng tốc độ. Có thể thay độ dài mỗi cạnh bằng một số nguyên không âm, trả chi phí bằng trị tuyệt đối của mức thay đổi. Hãy làm cho khoảng cách từ gốc đến mọi đầu nhận bằng nhau với tổng chi phí nhỏ nhất.

Input

Dòng đầu chứa $N$ và $M$ .
Với mỗi $i$ từ $2$ đến $N + M$ , dòng tiếp theo chứa $P_{i}$ và $C_{i}$ ; cạnh nối $P_{i}$ với $i$ có độ dài ban đầu $C_{i}$ .

Output

In một số nguyên là tổng chi phí nhỏ nhất.

Constraints

$1 \leq N, M$ .
$N + M \leq 3 \cdot 1 0^{5}$ .
$1 \leq P_{i} < i$ và $P_{i} \leq N$ .
$1 \leq C_{i} \leq 1 0^{9}$ .
Mỗi nút nối khác gốc có ít nhất một đỉnh con; các đầu nhận không có đỉnh con.
Độ dài mới của một cạnh có thể bằng $0$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $10$ test đầu có kích thước nhỏ, phù hợp với lời giải vét cạn độc lập.
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Ba khoảng cách ban đầu là $1, 4$ và $6$ . Chọn độ dài chung $4$ làm chi phí bằng $∣1 - 4∣ + ∣4 - 4∣ + ∣6 - 4∣ = 5$ , và trung vị cho thấy không giá trị chung nào tốt hơn.

Hàm chi phí của cây con: Với mỗi nút v, xét hàm F_v(x): chi phí nhỏ nhất bên trong cây con của v để mọi đầu nhận của cây con cách v đúng x. Các cây con độc lập khi x đã cố định, nên tại một nút nối, các hàm của con được cộng lại.
Hàm chi phí của cây con: Khi đi qua cạnh có độ dài ban đầu c, ta được chọn độ dài mới y>=0 và trả |y-c|. Đây là một phép min-convolution của hàm con với |y-c|. Các hàm vẫn lồi, tuyến tính từng đoạn, vì vậy có thể lưu bằng heap các breakpoint của đạo hàm.
Các thao tác heap: Một đầu nhận tạo hai breakpoint bằng độ dài cạnh của nó. Ở nút nối, ta hợp heap của các con bằng small-to-large, tương ứng với cộng các hàm lồi. Nếu nút có deg con, phép min-convolution qua cạnh cha loại các slope dương dư: bỏ deg-1 breakpoint lớn nhất, lấy hai breakpoint biên còn lại rồi cộng độ dài cạnh c vào chúng trước khi đưa lại heap.
Các thao tác heap: Tại gốc không có cạnh cha. Sau khi loại phần slope ứng với tất cả các nhánh của gốc, tổng các breakpoint dương còn lại được trừ khỏi tổng độ dài ban đầu; giá trị thu được là cực tiểu của hàm toàn cây.
Chứng minh đúng: Quy nạp từ các đầu nhận lên gốc. Với một đầu nhận, hàm theo khoảng cách qua cạnh duy nhất đúng là trị tuyệt đối quanh c, nên hai breakpoint khởi tạo là chính xác. Giả sử heap của các con biểu diễn đúng các hàm của chúng. Hợp heap cộng đúng các hàm vì đạo hàm của tổng bằng tổng đạo hàm.
Chứng minh đúng: Phép bỏ và dịch breakpoint là biểu diễn slope-trick chính xác của việc chọn một độ dài cạnh mới không âm rồi cộng |y-c|; nó giữ mọi phương án khả thi và lấy nhỏ nhất theo y. Do đó heap sau bước xử lý biểu diễn đúng F_v. Tại gốc, lấy cực tiểu của F_1 cho đúng chi phí nhỏ nhất làm mọi khoảng cách gốc-đầu nhận bằng nhau.
Độ phức tạp: Mỗi breakpoint được hợp small-to-large; cận thời gian O((N+M) log^2(N+M)), bộ nhớ O(N+M).