# ANOTHER_PP Editorial

Setter: Yash Thakker
Tester: Abhinav Sharma, Utkarsh Gupta
Editorialist: Pratiyush Mishra

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

cnt[U][j] - cnt[lca][j] > 0 \;AND\; cnt[V][j] - cnt[lca][j] > 0

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:

3 Likes

I am getting Runtime Error (Other) for the following submission. Is it because I am using too much memory? Thank you

https://www.codechef.com/viewsolution/65183780

i followed the same steps as described here, still getting WA. plz can someone help me…

my submission

I am getting Runtime Error . I think this is due to when LCA become “-1”. but i am unable to get that when LCA become “-1”.

if anyone know then pls provide me any testcase where it fail.

https://www.codechef.com/viewsolution/65235242