Approach for these problems

Can anyone tell me how to solve these two problems?

problem 1

and
problem 2

I saw the solutions of others but am unable to understand the approach.

Query on tree uses HLD of trees.
Avani and magic requires you to use Tries.
If you want author’s solutions for the problems, you can request below in the comments.

import java.io.;
import java.util.ArrayList;
/

  • @author rohan
    */
    class AVIMAGIC {
    public static void main(String[] args) throws java.io.IOException {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    int n=Integer.parseInt(br.readLine()),q,len,ch,tem[],arr[],size,index=0,root[],pre,pointer;
    StringBuilder m,ans,printing=new StringBuilder();
    ArrayList<int[]> vertex=new ArrayList<>();
    root=new int[7];
    root[5]=Integer.MAX_VALUE;
    vertex.add(root);
    size=1;
    for (int i = 0; i < n; i++) {
    m=new StringBuilder(br.readLine());
    m=m.append(‘'); len= m.length(); pointer=0; tem=vertex.get(0); while(len>0){ ch=m.charAt(pointer)-96; pointer++; if(tem[ch]==0){ arr=new int[7]; arr[5]=Integer.MAX_VALUE; vertex.add(arr); size++; tem[ch]=size-1; if(ch<tem[5]){ tem[5]=ch; } if(tem[6]<ch){ tem[6]=ch; } } tem=vertex.get(tem[ch]); len--; } } q=Integer.parseInt(br.readLine()); for (int i = 0; i < q; i++) { tem=vertex.get(0); ans=new StringBuilder(); pre=0; m=new StringBuilder(br.readLine()); m=m.append('’);
    len= m.length();
    pointer=0;
    arr=null;
    while(len>0){
    ch=m.charAt(pointer++)-96;
    if(tem[5]<ch){
    arr=tem;
    index=ch;
    pre=pointer-1;
    }
    tem=vertex.get(tem[ch]);
    len–;
    }
    tem=arr;
    if(tem==null){
    printing.append(“-1\n”);
    continue;
    }
    ans=ans.append(m.substring(0, pre));
    while (true) {
    if(tem[–index]!=0){
    ans.append((char)(index+96));
    tem=vertex.get(tem[index]);
    break;
    }
    }
    while(tem!=root){
    ans.append((char)(tem[6]+96));
    tem=vertex.get(tem[tem[6]]);
    }
    printing.append(ans.substring(0,ans.length()-2)).append(“\n”);
    }
    System.out.print(printing);
    }
    }
1 Like

thank you. Please provide the solution. That would help a lot.

Thanks alot

For Query on tree, you can refer to anybody’s solution. They are almost same.