Path between two nodes in graph having tree structure

general
,
1

Suppose a graph has N node. 1<=N<=10^5
You are being querried Q times with starting and ending node. 1<=Q<=10^6.

What should be the approach for this? I found DFS would not be suitable here.

Question says you have graph with N node and N-1 edges. Each edges is assigned a lowercase english letter string. Then you will be asked Q queries in which you will be given two nodes and you have to find that the string you collected from edges in between given node can form a palindromic string or not. String length will be less than 20

eg :
3
1 3 ab
1 2 abc

3
1 3
2 3
3 3

ans:
no
yes
yes

1 Like
2

What does each query ask in particular?

3

Link to Problem? :slight_smile:

4

It was a hiring contest problem which I already submitted so I dont have any link.

5

It was from SCRIBETECH contest from Hackerearth which was ended now.

6

Have you solved it?

7

there are N nodes and N-1 edges, assuming that the graph is not disconnected it will be a tress and there will be only one path between any two nodes.
Just treverse between those nodes and store each of the edge element you got in an array of size 20 then after getting the complete string check the array for being palindrome or not !