Page 1 of 212

UVa 11994. Happy Painting!

Brief description :

... 給定一棵 N 個結點的有根樹森林,邊上有一個顏色,需要支持下面這 3 個操作。

  • Query(x, y) 如果 x 和 y 在同一棵子樹中,則詢問路徑上邊的數目、和顏色的種類數。
  • Paint(x, y, c) 如果 x 和 y 在同一棵子樹中,則將經過的路徑上所有邊染色為 c。
  • Link(x, y, c) 如果 x 和 y 在同一個子樹中,且 x 不為 y 的祖先,那麼切斷 x 同其父親的聯繫,之後用一條顏色為 c 的邊連接 x、y。

(.. N = 50, 000 ..)

ゆっくり読んでください ...

Page 1 of 212