Untitled

#include <string>
#include <unordered_map>
#include <vector>
#define MAXL    (11)
#define SIZE 50000
#define HASH_SIZE 75007

using namespace std;

struct Species{
    int id;
    int rank;
    int child[5];
    int prev;
    //vector<int> next;

    Species(){
        rank = -1;
        for(int i = 0; i < 5; i++){
            child[i]  = 0;
        }
        prev = -1;
        //next.resize(0);
    }
} data[SIZE];

unordered_map<string, int> hashTable;
int index;

//int hashKey(char* str){
//    int index = 0;
//    while(*str != 0){
//        index = (index*31 + *str) % HASH_SIZE;
//        *str++;
//    }
//    
//    return index;
//}

void init(char mRootSpecies[MAXL])
{
    index = 0;
    hashTable = unordered_map<string, int>();
    for(int i = 0; i < SIZE; i++){
        data[i] = Species();
    }
    
    data[index].rank = 0;

    hashTable[ mRootSpecies] = index;
}

void add(char mSpecies[MAXL], char mParentSpecies[MAXL])
{
    index++;
    hashTable[mSpecies] = index;
    int idP = hashTable[mParentSpecies];
    

    data[index].rank = data[idP].rank + 1;
    data[index].prev = idP;
    //hashTable[idP].next.push_back(id);

    int tmpParent = index;
    for(int i = 1; i <= 4; i++){
        tmpParent = data[tmpParent].prev;
        if(tmpParent == -1) break;
        data[tmpParent].child[i]++;
    }
}

int findParent(int id1, int id2)
{
    if(id1 == id2)
        return id1;
    if(data[id1].prev == data[id2].prev){
        return data[id1].prev;
    }
    if(data[id1].rank > data[id2].rank){
        return findParent(data[id1].prev, id2);
    }
    if(data[id1].rank < data[id2].rank){
        return findParent(id1, data[id2].prev);
    }
    return findParent(data[id1].prev, data[id2].prev);
}

int getDistance(char mSpecies1[MAXL], char mSpecies2[MAXL])
{
    int cnt = 0;
    int id1 = hashTable[mSpecies1];
    int id2 = hashTable[mSpecies2];
    if(data[id1].rank == 0)
        return data[id2].rank;
    if(data[id2].rank == 0)
        return data[id1].rank;
    int idP = findParent(id1, id2);

    cnt = data[id1].rank - data[idP].rank + data[id2].rank - data[idP].rank;
    return cnt;
}

int getCount(char mSpecies[MAXL], int mDistance)
{
    int id = hashTable[mSpecies];
    int cnt =data[id].child[mDistance];

    if(data[id].rank == 0) return cnt;

    int curId = id;
    int prevId;
    int needCnt;
    for(int i = 1; i <= mDistance; i++){
        if(data[curId].rank == 0) break;

        prevId = data[curId].prev;
        needCnt = mDistance - i;

        if(needCnt == 0) cnt++;
        else if(needCnt == 1){
            cnt += data[prevId].child[needCnt] - 1;
        }
        else{
            cnt += data[prevId].child[needCnt] - data[curId].child[needCnt-1];
        }

        curId = prevId;
    }
    return cnt;
}
///
Java
package Phylogenetic_Tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class UserSolution
{
	public class Node{
		String id;
		int level;
		Node parent;
		int[] child;
		public Node() {	
			this.level=0;
			this.child = new int[5];
		}
		
	}
	Node findParent(Node n1,Node n2){
		if(n1==n2){
			return n1;
		}
		if(n1.parent==n2.parent){
			return n1.parent;
		}
		else if(n1.level>n2.level){
			return findParent(n1.parent, n2);
		}
		else if(n1.level<n2.level){
			return findParent(n1, n2.parent);
		}
		return findParent(n1.parent, n2.parent);
	}
	String charttoString(char[] a) {
		int i = 0;
		String str = "";
		while (a[i] != '\0') {
			str += a[i];
			i++;
		}
		return str;
	}
	HashMap<String, Node> nodeMap=new HashMap<String, UserSolution.Node>();
	public void init(char[] mRootSpecies)
	{
		nodeMap.clear();
		Node root=new Node();
		root.id=charttoString(mRootSpecies);
		nodeMap.put(charttoString(mRootSpecies), root);
		
	}

	public void add(char[] mSpecies, char[] mParentSpecies)
	{
		Node node=new Node();
		node.id=charttoString(mSpecies);
		Node Nparent=nodeMap.get(charttoString(mParentSpecies));
		int a=Nparent.level+1;
		node.level=a;
		node.parent=Nparent;
		Node new_node=node;
		for(int i=1;i<5;i++){
			new_node=new_node.parent;
			nodeMap.remove(new_node);
			if(new_node==null){
				break;
			}
			new_node.child[i]++;
//			node.child[i]++;
			nodeMap.put(new_node.id, new_node);
		}
		nodeMap.put(node.id, node);
		
	}
	
	public int getDistance(char[] mSpecies1, char[] mSpecies2)
	{
		int ans=0;
		Node n1=nodeMap.get(charttoString(mSpecies1));
		Node n2=nodeMap.get(charttoString(mSpecies2));
		Node parent=findParent(n1, n2);
		if(parent!=null){
		ans=n1.level+n2.level-2*parent.level;}
		else{
			ans=n1.level+n2.level;
		}
		return ans;
	}
	
	public int getCount(char[] mSpecies, int mDistance)
	{
		Node node=nodeMap.get(charttoString(mSpecies));
		Node parent=new Node();
		int ans=node.child[mDistance];
		parent=node;
		for(int i=1;i<=mDistance;i++){
			Node node1=parent;
			parent=parent.parent;
			if(parent==null){
				break;
			}
			int index=mDistance-i;
			if(index==0){
				ans++;
			}
			else if(index==1){
				ans+=parent.child[index]-1;
			}
			else if(index>1){
				ans+=parent.child[index]-node1.child[index-1];
			}
//			if(mDistance-(node.level-parent.level)==1){
//				ans+=parent.child[mDistance-(node.level-parent.level)]-1;
//			}
//			else if(mDistance-(node.level-parent.level)>1){
//			if(parent.child[mDistance-(node.level-parent.level)]!=0){
//				ans+=parent.child[mDistance-(node.level-parent.level)]-node1.child[mDistance-(node.level-parent.level)-1];
//			}
//			}
		}
		return ans;
	}
}