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.