給定一個物種演化圖，關(guān)系的表示方式如下：x y : 表示x為y的先祖。一個物種只會有一個先祖，一個先祖可以有很多個演化出來的物種，請你找出每個問題詢問物種的祖父物種(先祖的先祖)，每個物種會使用一個不重復(fù)的編號來表示，如果該物種沒有祖父物種的話或是不存在，那么請將他的祖父物種當是0。(憑空而生)保證所有物種間一定有所關(guān)連，且不會有重復(fù)演化的現(xiàn)象發(fā)生，即演化圖只會是一棵樹。輸入格式:只有一組測資。第一行會有兩個數(shù)字N、Q，代表總共有N個物種及Q個問題。接下來N-1行，每一行有兩個數(shù)字x、y，意義如題目所述。接下來的Q行，每一行有一個數(shù)字Z，代表要詢問的物種編號。測資范圍：1 < N < 100000 < Q < 10000 < x, y, z < 1000000輸出格式：對于每一個詢問的物種編號，將他們的祖父物種編號加總后再輸出。輸入樣例：6 31000 20001000 30002000 40003000 50005000 6000500060001234輸出樣例：4000時間限制：100ms內(nèi)存限制：16000kb

#include <stdio.h>#include <string.h>int main(){  int arrBucket[1000000];  int N, Q;  int x, y, z;  long long sum = 0;  memset(arrBucket, 0, sizeof(arrBucket));  scanf("%d %d", &N, &Q);  while(N -- > 1){    scanf("%d %d", &x, &y);    arrBucket[y] = x;  }  while(Q --){    scanf("%d", &z);    if(arrBucket[z] != 0){      if(arrBucket[arrBucket[z]] != 0){        sum += arrBucket[arrBucket[z]];      }    }  }  printf("%lld", sum);  return 0;}

#include <stdio.h>#include <stdlib.h>#define NULLKEY -1typedef struct {  int *elem; //元素   int *elemP; //父元素   int count;}HashTable;int Hash(HashTable H, int k){  return k % H.count;}void InitHashTable(HashTable *H){  int i;  H->elem = (int *)malloc(sizeof(int) * H->count);  H->elemP = (int *)malloc(sizeof(int) * H->count);  for(i = 0; i < H->count; i ++){    H->elem[i] = NULLKEY;    H->elemP[i] = NULLKEY;   }}void InsertHash(HashTable *H, int key, int value){  int addr;  addr = Hash(*H, key);  while(H->elem[addr] != NULLKEY){    addr = (addr + 1) % H->count;  }  H->elem[addr] = key;  H->elemP[addr] = value;}int FindHash(HashTable *H, int key, int *addr){  *addr = Hash(*H, key);  while(H->elem[*addr] != key){    *addr = (*addr + 1) % H->count;    if(H->elem[*addr] == NULLKEY || *addr == Hash(*H, key)){      return 0;    }  }  return 1;}int main(){  int N, Q;  int x, y, z, addr;  long long sum = 0;  HashTable H;  scanf("%d %d", &N, &Q);  H.count = N - 1;  InitHashTable(&H);  while(N -- > 1){    scanf("%d %d", &x, &y);    InsertHash(&H, y, x);  }  while(Q --){    scanf("%d", &z);    if(FindHash(&H, z, &addr)){      if(FindHash(&H, H.elemP[addr], &addr)){        sum += H.elemP[addr];      }    }  }  printf("%lld", sum);  return 0;}

#include <iostream>#include <map>using namespace std;int main() {  int n, q;  cin >> n >> q;  map<int,int> mp;   map<int,int>::iterator it;  int x, y, z;  for (int i=1; i<n; ++i) {      cin >> x >> y;    mp.insert(pair<int,int>(y,x));    }  int sum = 0;  for (int i=0; i<q; ++i) {    cin >> z;    it = mp.find(z);      if (it != mp.end()) {      it = mp.find(it->second);        if (it != mp.end())        sum += it->second;      }  }  cout << sum;  return 0;}