A20250306a_DEshaw

import java.util.*;

/*

given you a tree
each node containing a character
find count of all the vertical paths start from root node
which can be formed as a palindrome
 */
/**
 important point to understand here -

assume you have a tree like below


                        a
                        |
                        a
                       / \
                      c   d
                          |
                          f
                          |
                          d
the valid paths from root node that can become palindrome are

a
a a
a a d
a a d f d
a a c

with simple dfs and hashmap , you can easily solve this
as you traverse the children of the node
pass the current hasmap with curr node freq added
when curr node has odd freq count <=1
then the current path is valid otherwise go on ...


 */

/*

//inputs for node characters and tree connections
a a c d f d
6 5
0 1
1 2
1 3
3 4
4 5

expected output -
The result is 5


 */


@SuppressWarnings({"unused","unchecked"})
public class A20250306a_DEshaw  {

    static Scanner sc = new Scanner(System.in);

    private static int[] getArray() {
        String[] sArr = sc.nextLine().split(" ");
        int[] arr = Arrays.stream(sArr).mapToInt(Integer::parseInt).toArray();
        return arr;
    }

    private static char[] getCharArray() {
        String[] sArr = sc.nextLine().split(" ");
        char[] cArr = new char[sArr.length];
        for (int i = 0; i < sArr.length; i++) {
            cArr[i] = sArr[i].charAt(0); // Take the first character of each string
        }
        return cArr;
    }

    private static int getMax(int[] arr) {
        int currMax = Integer.MIN_VALUE;
        for (int curr : arr) {
            currMax = Math.max(currMax, curr);
        }
        return currMax;
    }

    public static void getCount(int currInd,ArrayList<Integer>[] adjList,HashMap<Character,Integer> fMap,
    int[] ans,
    char[] charValues,
    int[] visited){
        char currChar = charValues[currInd];
        int currFreq = fMap.getOrDefault(currChar,0) +1;
        if(currFreq%2==0){//that means odd became even
            ans[1] -= 1;
        }else{//even became now odd
            ans[1] += 1;
        }
        if(ans[1]<=1){// odd count is in control , we still can make a palindrome
            ans[0] += 1;
        }
        fMap.put(currChar,currFreq);
        // System.out.println("map is "+fMap);
        // System.out.println("oddcount is"+ ans[1]+"  for currChar "+currChar);

        // System.out.println("ans is"+ ans[0]);
        visited[currInd] = 1;
        for(int child:adjList[currInd]){
            if(visited[child] == 1){
                continue;
            }
            getCount(child,adjList,fMap,ans,charValues,visited);
        }
        visited[currInd] = 0;
        currFreq-=1;
        //it is important to correct the oddCount too
        if(currFreq%2==0){//that means odd became even
            ans[1] -= 1;
        }else{//even became now odd
            ans[1] += 1;
        }
        fMap.put(currChar,currFreq);
        return;
    }

    public static void main(String args[]) {
        // prepare the inputs


        // int[] visitable = getArray();
        char[] charValues = getCharArray();
        int[] tempArr = getArray();

        int nodes = tempArr[0];
        int edges = tempArr[1];
        ArrayList<Integer>[] adjList =(ArrayList<Integer>[]) new ArrayList[nodes];//explicit type conversion
        for(int i =0;i<nodes;i+=1){
            adjList[i] = new ArrayList<>();
        }
        int temp = edges;
        //fill up the graph
        while(temp!=0){
            temp-=1;
            tempArr = getArray();
            int n1 = tempArr[0];
            int n2 = tempArr[1];
            adjList[n1].add(n2);
            adjList[n2].add(n1);
        }
        HashMap<Character,Integer> fMap = new HashMap<>();
        int[] visited = new int[nodes];
        int[] ans = new int[2];//1st index to maintain ans second to maintain odd freq count
        getCount(0,adjList,fMap,ans,charValues,visited);
        int res = ans[0];


        System.out.println("The result is " + res);

    }
}

class Pair{
    int row;
    int col;
    public Pair(int i,int j){
        this.row = i;
        this.col = j;

    }
}