Refund Decision Tree Evaluation

Problem: Refund Decision Tree Evaluation DoorDash has an automatic refund system. The system uses a binary decision tree to decide the outcome for each refund request. Each internal node represents a boolean condition, for example: is_late == true missing_items >= 2 order_value > 50 Each leaf node represents a final decision, for example: NO_REFUND PARTIAL_REFUND FULL_REFUND ESCALATE Given a decision tree and multiple refund requests, output the decision for each request. Input Format The first line contains two integers N Q: N: the number of decision-tree nodes. Nodes are numbered from 1 to N, and node 1 is the root. Q: the number of refund requests. The next N lines describe the nodes. Each line has one of two formats: Internal Node I field op value left right Meaning: evaluate whether field op value is true for the request. If true, go to child left. If false, go to child right. op can be: == != < <= > >= Leaf Node L result Meaning: output result when this node is reached. The next Q lines describe refund requests: K key1=value1 key2=value2 ... keyK=valueK K is the number of fields. Field values have three possible types: Boolean: true or false Integer: e.g. 10 String: e.g. US, VIP Comparison Rules == and != can be used for booleans, integers, and strings. < <= > >= are only used for integers. Every field used by an internal node is guaranteed to exist in every request. The decision tree is guaranteed to be valid: no cycles and all child references are valid. Output Format Output Q lines. The i-th line is the decision for the i-th refund request. Constraints 1 <= N <= 10^5 1 <= Q <= 10^5 Number of fields per request: 1 <= K <= 50 Decision tree height is at most 10^4 All input strings have length at most 50 Example Input: 5 3 I is_late == true 2 3 L FULL_REFUND I missing_items >= 2 4 5 L PARTIAL_REFUND L NO_REFUND 2 is_late=true missing_items=0 2 is_late=false missing_items=3 2 is_late=false missing_items=1 Output: FULL_REFUND PARTIAL_REFUND NO_REFUND Example Input 5 3 I is_late == true 2 3 L FULL_REFUND I missing_items >= 2 4 5 L PARTIAL_REFUND L NO_REFUND 2 is_late=true missing_items=0 2 is_late=false missing_items=3 2 is_late=false missing_items=1 Output FULL_REFUND PARTIAL_REFUND NO_REFUND