import java.util.HashMap;

public class Tree {
    private Node root;

    public Tree(){

        root = new Node();
    }


    public int distinct(String k){
        char letter;
        int distinct = 0;
        Node node = null;
        HashMap<Character, Node> children = root.children;

        for(int i = 0; i < k.length(); i++){
            letter = k.charAt(i);
            if(children.containsKey(letter)){
                node = children.get(letter);
                children = node.children;
            }
        }

        if(node != null){
            if(node.value > 0) distinct++;
            for(HashMap.Entry<Character, Node> child : children.entrySet()){
                if(child.getValue().value > 0) distinct++;
                distinct += distinct(child.getValue());
            }
        }

        return distinct;
    }


    private int distinct(Node node){
        int distinct = 0;

        if(node != null){
            for(HashMap.Entry<Character, Node> child : node.children.entrySet()){
                if(child.getValue().value > 0) distinct++;
                distinct += distinct(child.getValue());
            }
        }

        return distinct;
    }

    public int count(String k){
        char letter;
        int count = 0;
        Node node = null;
        HashMap<Character, Node> children = root.children;

        for(int i = 0; i < k.length(); i++){
            letter = k.charAt(i);
            if(children.containsKey(letter)){
                node = children.get(letter);
                children = node.children;
                if(i == k.length()-1) count += node.value;
            }

        }

        if(node != null){
            for(HashMap.Entry<Character, Node> child : children.entrySet()){
                count += child.getValue().value;
                count += count(child.getValue());
            }
        }

        return count;
    }

    private int count(Node node){
        int count = 0;

        if(node != null){
            for(HashMap.Entry<Character, Node> child : node.children.entrySet()){
                count += child.getValue().value;
                count += count(child.getValue());
            }
        }

        return count;
    }


    public void put(String k){
        HashMap<Character, Node> children = root.children;
        for(int i = 0; i < k.length(); i++){
            char key = k.charAt(i);
            Node diffNode;
            if(children.containsKey(key)){
                diffNode = children.get(key);
            }
            else{
                diffNode = new Node(key);
                children.put(key, diffNode);
            }
            children = diffNode.children;

            if(i == k.length()-1) {
                diffNode.leaf = true;
                diffNode.increment();
            }
        }
    }

    public Integer get(String k){
        char letter;
        Integer val = 0;
        Node node;
        HashMap<Character, Node> children = root.children;

        for(int i = 0; i < k.length(); i++){
            letter = k.charAt(i);
            if(children.containsKey(letter)){
                node = children.get(letter);
                val = node.value;
                children = node.children;
            }
            else return 0;
        }
        return val;
    }

    private class Node{
        char key;
        Integer value = 0;
        boolean leaf;
        HashMap<Character, Node> children = new HashMap<>();

        public void increment(){
            value++;
        }

        public Node(){}
        public Node(Character key){
            this.key = key;
        }
    }
}