Phylogenetic Tree

[qiaobaaa]

include

include

using namespace std;

define MAXL (11)

define SPC_MAX 50001

struct MyStruct { int parent; int child_num[5]; }species[SPC_MAX];;

unordered_map<string, int> umap; int cnt;

void init(char mRootSpecies[MAXL]) { cnt = 1; umap.clear();
for (int i = 0; i < SPC_MAX; i++) { species[i].parent = -2; for (int j = 0; j < 5; j++) { species[i].child_num[j] = 0; } } umap[mRootSpecies] = cnt; species[cnt].parent = -1; species[cnt].child_num[0] = 1; cnt++; }

void add(char mSpecies[MAXL], char mParentSpecies[MAXL]) { umap[mSpecies] = cnt;
int pid = umap[mParentSpecies]; species[cnt].parent = pid; species[cnt].child_num[0] = 1; for (int i = 1; i < 5; i++) { if (pid == -1) break;
species[pid].child_num[i]++; pid = species[pid].parent; } cnt++; }

int getDistance(char mSpecies1[MAXL], char mSpecies2[MAXL]) { int idx1 = umap[mSpecies1]; int idx2 = umap[mSpecies2]; int count = 0;

while (idx1 != idx2) {
    if (idx1 > idx2) {
        idx1 = species[idx1].parent;
    }
    else {
        idx2 = species[idx2].parent;
    }
    count++;
}
return count;

}

int getCount(char mSpecies[MAXL], int mDistance) { int dst = mDistance; int cur = umap[mSpecies]; int pid = species[cur].parent; int count = species[cur].child_num[dst]; //不是根节点的处理情况，是根节点直接返回 while (dst > 0 && pid != -1) { count += species[pid].child_num[dst - 1]; if (dst - 1 > 0) { count -= species[cur].child_num[dst - 2]; } dst--; cur = pid; pid = species[pid].parent; } return count; }