How to solve "QTREE4 — Query on a tree IV SPOJ"?

Правка en2, от Peregrine_Falcon, 2019-09-13 14:52:38

I've learned Heavy light decomposition and found This Problem on Anudeep's blog. I couldn't come up any idea how to solve this problem.

Given a undirected weighted tree with N nodes ( N <= 1e5 )

All the nodes are white initially.

And Q queries ( Q <= 1e5 )

Update — Change the color of given node ( Black to White or White to Black )

Query — If there are at least one node with white color, find the maximum distance between any two nodes ( a , b ). a == b can be allowed.

Cost of edges can be negative.

Thank You.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Peregrine_Falcon 2019-09-13 14:52:38 39
en1 Английский Peregrine_Falcon 2019-09-13 14:50:12 690 Initial revision (published)