I came across this question and as much as I researched I feel it is related to HLD and segtree.
I have basic knowledge of HLD and thus was hoping if someone can share code or some explaination so that I could learn from that.
I’d provide the gist of question
Question: ( this came in one of hiring rounds )
You are given a tree with n nodes, nodes are numbered from 1 to n.
Each node can be associated with a color( red / black),
Initially all nodes are colored red.
You are given q queries passed with a query types and a node number
query can be of 3 types ( 1/2/3),
query 1) paint red on entire subtree on node P (expluding P)
query 2) paint black on entire subtree of node P ( excluding P)
query 3) return count of red nodes in subtree of P( excluding P)
Range n<=1e5 ; q<=1e5.
Thoughts:
I feel this has to be done with subtree queries with HLD on a tree/ few cf blogs suggest using euler path for such type of queries. But currently I dont have code/ idea how to implement this.
Any guidance will be appreciated.
Thanks.