Hello, now I'm having to face a Problem that can be shortly restate as:
Given n,k,q <= 2e5
There is a tree of n nodes. And k pair of nodes on the tree that are colored red Q queries: Given a node S. We have to find the number of nodes T that on the way from S to T there must be at least one pair of nodes with the color of red(from the k pairs given)
INPUT: -n,k,q -n — 1 lines: edge of tree, connecting 2 nodes u and v -k pair of red nodes -Q queries: each line contains a node S OUTPUT On Q lines print the number of available T nodes **** My idea First, Apply the Euler tour so that I can easily update the value of each node. And for each pair of u,v (one of the k pairs) - if u is ancestor of v --> update all nodes u can travel from u, but not on the way from u to v as the number of children of V --> update all the children of v as the number of nodes can travel to from u but not passing the path from u to v. -_if u and v are neither not ancestor of the other_ -->update all nodes u can travel to from u equal to (not passing the path from u to v) by the num of children of v -->do the same as V
I want to ask that,is there any way to rapidly count the number of nodes from u or v that doesnt lie on the path between them.__
