trang chủ / đề bài / prevoi25_c1_treasure

Kho báu

Đề bài

Mô tả

Một vùng biển bao gồm n hòn đảo đánh số từ 1 đến n và được kết nối bởi n−1 tuyến đường biển. Từ một hòn đảo bạn có thể đến được mọi hòn đảo khác chỉ qua các tuyến đường này.

Mỗi hòn đảo thuộc địa phận của chính xác một quốc gia, các quốc gia được đánh số từ 1 đến n. Hòn đảo v thuộc địa phận của quốc gia tv. Lưu ý một quốc gia có thể bao gồm bất kì tập con các hòn đảo nào, và có thể bạn không thể di chuyển giữa hai hòn đảo cùng quốc gia chỉ bằng cách đi qua các hòn đảo cùng quốc gia khác.

Bạn là một thợ săn kho báu và đang sinh sống ở hòn đảo 1. Mỗi hòn đảo có một mức thuế nhất định cho mỗi kho báu bạn mang qua. Ở hòn đảo v, mức thuế là cv đồng.

Bạn được biết hai loại sự kiện sau có thể xảy ra:

  1. Hòn đảo v trở thành địa phận của quốc gia tnew.
  2. Có k kho báu sẽ xuất hiện ở các hòn đảo a1,a2,…,ak, khi đó bạn sẽ di chuyển đến tất cả các hòn đảo này và mang kho báu ở từng hòn đảo về hòn đảo 1 (theo đường đi duy nhất trên các tuyến đường biển). Sau đó bạn sẽ chọn một hòn đảo v bất kì thuộc địa phận của quốc gia t và bạn sẽ chỉ phải trả thuế cv·numv đồng với numv là số lượng kho báu bạn mang qua hòn đảo v. Kho báu xuất hiện ở hòn đảo ai được tính là mang qua chính hòn đảo ai và mọi hòn đảo trên đường từ ai về hòn đảo 1 (kể cả hòn đảo 1).

Với mỗi sự kiện loại 2, bạn cần tính mức thuế lớn nhất mà bạn phải trả trên một hòn đảo bất kì thuộc quốc gia t, tức là giá trị lớn nhất của cv·numv trên các hòn đảo v đang thuộc quốc gia t. Nếu không có hòn đảo nào thuộc quốc gia t thì mức thuế bạn phải trả là 0.

Các sự kiện loại 1 có hiệu lực lâu dài: chúng ảnh hưởng đến mọi sự kiện xảy ra sau đó.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và q (2≤n≤200000, 1≤q≤200000): số lượng hòn đảo và số lượng sự kiện.
  • Dòng thứ hai chứa n−1 số nguyên p2,p3,…,pn (1≤pi<i), trong đó pi có nghĩa là có một tuyến đường biển giữa hòn đảo i và hòn đảo pi.
  • Dòng thứ ba chứa n số nguyên t1,t2,…,tn (1≤ti≤n), trong đó hòn đảo i thuộc địa phận của quốc gia ti.
  • Dòng thứ tư chứa n số nguyên c1,c2,…,cn (1≤ci≤109): mức thuế tương ứng của từng hòn đảo.
  • q dòng tiếp theo, mỗi dòng bắt đầu bằng số nguyên xi (1≤xi≤2) là loại sự kiện:
    • Nếu xi=1, tiếp theo là hai số nguyên v và tnew (1≤v,tnew≤n), có nghĩa là v trở thành địa phận của quốc gia tnew.
    • Nếu xi=2, tiếp theo là hai số nguyên t và k, sau đó là k số nguyên a1,a2,…,ak (1≤t,k,ai≤n), trong đó t là quốc gia mà bạn phải chọn một hòn đảo để đóng thuế, k là số lượng hòn đảo có kho báu, và ai là các hòn đảo chứa kho báu. Bộ test đảm bảo các ai trong cùng một sự kiện đều khác nhau và tổng k trong các sự kiện loại 2 không vượt quá 200000.

Dữ liệu ra

Với mỗi sự kiện loại 2, theo thứ tự xuất hiện, in ra trên một dòng mức thuế lớn nhất mà bạn phải đóng. Nếu không có hòn đảo nào thỏa mãn thì in ra 0.

Ràng buộc

  • 2≤n≤200000, 1≤q≤200000.
  • 1≤pi<i.
  • 1≤ti≤n, 1≤ci≤109.
  • 1≤v,tnew≤n; 1≤t,k,ai≤n, các ai trong một sự kiện đôi một khác nhau.
  • Tổng k trong các sự kiện loại 2 không vượt quá 200000.

Subtasks

  • Subtask 1 (18% số điểm): n,q,∑ki≤1000.
  • Subtask 2 (14% số điểm): không có sự kiện loại 1 và ti=1 với mọi i.
  • Subtask 3 (10% số điểm): không có sự kiện loại 1.
  • Subtask 4 (18% số điểm): pi=i−1.
  • Subtask 5 (18% số điểm): pi=⌊i2⌋.
  • Subtask 6 (22% số điểm): không có ràng buộc gì thêm.

Ví dụ

Input Output Giải thích
4 4
1 2 2
1 1 3 3
2 3 10 7
2 3 2 3 4
2 1 2 4 3
1 3 1
2 1 2 3 4
10
6
10
Sự kiện thứ nhất: kho báu ở đảo 3 và 4, đóng thuế ở quốc gia 3 gồm đảo 3 và 4, mỗi đảo được mang kho báu qua đúng một lần, đáp án c3·1=10. Sự kiện thứ hai: quốc gia 1 gồm đảo 1 và 2, cả hai được mang kho báu qua hai lần, đáp án c2·2=6. Sự kiện thứ ba: đảo 3 chuyển sang quốc gia 1. Sự kiện thứ tư: quốc gia 1 gồm đảo 1,2,3; đảo 1,2 được mang qua hai lần, đảo 3 một lần, đáp án c3·1=10.
5 5
1 1 3 3
2 1 2 1 1
4 9 1 5 6
2 2 3 4 5 2
2 1 2 4 5
1 5 3
2 1 3 4 5 2
2 4 1 1
12
6
9
0
Sự kiện 1: num1=3, num3=2, quốc gia 2 gồm đảo 1 và 3, đáp án max(4·3,1·2)=12. Sự kiện 2: quốc gia 1 gồm đảo 2,4,5 với num lần lượt 0,1,1, đáp án c5=6. Sự kiện 3: đảo 5 rời quốc gia 1. Sự kiện 4: đáp án c2·1=9 (đảo 5 không còn tính). Sự kiện 5: quốc gia 4 không có hòn đảo nào, đáp án 0. (Ví dụ này không có trong đề gốc.)

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0