Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QTREEX - Truy vấn trên cây

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qtreex


Cho một cây gồm N nút đánh số từ 1->N. Các cạnh của cây đánh số từ 1->N-1, mỗi cạnh có trọng số là một số nguyên. Bạn cần viết chương trình thực hiện dãy các lệnh sau:
CHANGE i v => Thay đổi trọng số của cạnh thứ i thành v
NEGATE a b => Đảo dấu trọng số của tất cả các cạnh nằm trên đường đi từ a đến b
QUERY a b => Tìm trọng số lớn nhất của các cạnh nằm trên đường đi từ a đến b

Input

Input là một bộ gồm nhiều test. Dòng đầu của input là số test t ( t<=20 ). Tiếp sau đó là các test.
Mỗi test bắt đầu bằng một dòng trống. Dòng tiếp theo ghi một số N ( N<=10000 ). N-1 dòng tiếp theo, mỗi dòng ghi 3 số a, b và c mô tả một cạnh của cây nối a với b và có trọng số là c. Thứ tự của các cạnh chính là thứ tự xuất hiện trong input. Tiếp theo là dãy các lệnh như mô tả ở trên(số lệnh không quá 50000). Cuối mỗi test ghi một từ "DONE".
Dữ liệu vào luôn đảm bảo trọng số của các cạnh ở mỗi thời điểm có giá trị tuyệt đối không vượt quá 10000000.

Output

Với mỗi lệnh "QUERY", in ra kết quả tìm được. Nếu a = b thì ghi ra 0.

Example

Input:
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Output:
1
3

Được gửi lên bởi:VOJ problem setters
Ngày:2007-09-21
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Ðược add lên bởi Khúc Anh Tuấn

hide comments
2020-06-27 13:59:50
Tham khảo:
Solution: http://megaurl.in/mz5xz
Code: http://megaurl.in/kOnchd4W
2019-12-25 14:55:26
dùng LCA lúc nào cũng SIG
2019-09-08 19:59:39
thề luôn code xong bày này t chạy quanh phòng luôn. code mất mẹn hơn 200 dòng :(((
p/s: bạn phía dưới tức đổi âm thành dương, dương thành âm á

Hoangkings100 t1k28 vô đối !

Last edit: 2019-09-08 20:00:12
2018-07-27 17:40:01
NEGATE a b => Đảo dấu trọng số của tất cả các cạnh nằm trên đường đi từ a đến b
// là sao vậy mọi người
2018-01-02 10:04:39
Đậu moé quên memset =.= mất mịa 1 đấm AC (3 đấm mới AC) *cry*
ko cần 1 dòng trống như bên dưới nha ^^
200 dòng
frostpixel aka.How 2 AC

Last edit: 2018-09-20 10:56:40
2017-12-15 16:25:25
giữa các test nhớ xuất ra 1 dòng trống :v
2017-11-14 02:05:04
heavy light
2017-09-16 14:09:12
biết là lazy propagation nhưng méo biết làm
2017-07-19 03:21:16
bài này dùng IT hả các bác?
2017-07-05 12:03:02
baif nhuw loz
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.