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.
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.