PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Yash Thakker
Tester: Abhinav Sharma, Utkarsh Gupta
Editorialist: Pratiyush Mishra
DIFFICULTY:
2555
PREREQUISITES:
Trees, Dynamic Programming
PROBLEM:
Chef is given a rooted tree with N nodes numbered 1 to N where 1 is the root node.
Each node is assigned a lowercase english alphabet between a to z (both included).
Given two nodes A and B:
- Let LCA(A, B) denote the lowest common ancestor of nodes A and B.
- Let DIS(A,B) denote the string containing all the characters associated with the nodes in the same order as the shortest path from node A to node B (excluding the character associated to node B). Note that DIS(A,A) is an empty string.
Chef needs to answer Q queries. Each query is of the type:
- U V: Given two integers U and V (1\leq U,V \leq N), determine if there exist a concatenation of a non-empty subsequence of DIS(U,LCA(U,V)) and a non-empty subsequence of DIS(V,LCA(U,V)) such that it is a palindrome.
EXPLANATION:
The first thing that needs to be done is to pre-calculate lowest common ancestors for all nodes using binary lifting so that we can find the lowest common ancestor for any two nodes in log(N) time. More details regarding that can be found here
Along with that, we also define another variable cnt[node][x] that stores frequency of character x from root till node. This can be again done using DFS.
Once we are done with both these preprocessing, we can solve for each query in log(N) time. Say for a query we are given U and V, we can calculate their lowest common ancestor from the algorithm above. Let that be lca. Now for concatenation of a particular subsequence of DIS(U,lca) and DIS(V,lca) to be a palindrome they both need to have at least one character common, i.e DIS(U,lca) and DIS(V,lca) should have one character in common say a since then our final string can be aa which is a palindrome.
Thus for each query we loop through all characters from a to z and say for a particular character j if
then that implies they both have character j common and so we can form a palindrome string.
TIME COMPLEXITY:
O(Qlog(N)), for each test case.
SOLUTION:
Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution