BNUOJ 34717 Klingon Warfare

http://acm.bnu.edu.cn/contest/problem_show.php?pid=34717

給兩個有根樹，子樹有序

找出最大的同構子樹的大小


TREE HASH

然後重點應該是rk會炸

http://wenku.baidu.com/view/4eb07f3283c4bb4cf7ecd125.html

在乘上數字後需要做非線性的處理

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef unsigned long long int int64;
typedef pair<int64, int64> p64;
const int64 P1 = 12345678907LL;
const int64 P2 = 12345678981LL;
vector<int> to1[10200], to2[10200];
int type1[10200], type2[10200];
int cnt1[10200], cnt2[10200];
int64 rh[10000];
set<pair<p64, int> > hash1;
p64 gethash1(int nd){
 int64 sz = to1[nd].size();
 //printf("vis at %d\n", nd);
 int64 tc1 = (int64)type1[nd], // + sz*100 + 514,
   tc2 = (int64)type1[nd];// + sz*100 + 514;
 int ccnt = 1;
 for(int lx = 0;lx < to1[nd].size();lx++){
  p64 rt = gethash1(to1[nd][lx]);
  tc1 = ((tc1*rh[lx])%P1  + rt.first)%P1;
  tc1^= rh[9999-lx];
  tc2 = ((tc2*rh[lx])%P2  + rt.second)%P2;
  tc2^= rh[9999-lx];
  ccnt += cnt1[to1[nd][lx]];
 }
 //tc1 = ((tc1*10000LL)%P1 + (int64)to1[nd].size())%P1;
 //tc2 = ((tc2*10000LL)%P2 + (int64)to1[nd].size())%P2;
 cnt1[nd] = ccnt;
 hash1.insert(pair<p64,int>(p64(tc1, tc2) ,cnt1[nd]));
 return p64(tc1, tc2);
}
int res = 0;
p64 gethash2(int nd){
 int64 sz = to2[nd].size();
 int64 tc1 = (int64)type2[nd], // + sz*100 + 514,
   tc2 = (int64)type2[nd];// + sz*100 + 514;
 int ccnt = 1;
 for(int lx = 0;lx < to2[nd].size();lx++){
  p64 rt = gethash2(to2[nd][lx]);
  tc1 = ((tc1*rh[lx])%P1  + rt.first)%P1;
  tc1^= rh[9999-lx];
  tc2 = ((tc2*rh[lx])%P2  + rt.second)%P2;
  tc2^= rh[9999-lx];
  ccnt += cnt2[to2[nd][lx]];
 }
 //tc1 = ((tc1*10000LL)%P1 + (int64)to2[nd].size())%P1;
 //tc2 = ((tc2*10000LL)%P2 + (int64)to2[nd].size())%P2;
 cnt2[nd] = ccnt;
 if(hash1.count(pair<p64, int>(p64(tc1, tc2), cnt2[nd])) )
  res = max(res, cnt2[nd]);
 return p64(tc1, tc2);
}
int main()
{
 for(int lx = 0;lx < 10000;lx++)
  rh[lx] = rand()%7122 + 31;
 int T;scanf("%d", &T);
 while(T--){
  res = 0;
  int n1, n2; scanf("%d %d", &n1, &n2);
  hash1.clear();
  for(int lx = 0;lx <= n1;lx++) to1[lx].clear();
  for(int lx = 0;lx <= n2;lx++) to2[lx].clear();
  char inpstr[100]; int par;
  for(int lx =  0;lx < n1;lx++){
   scanf("%s %d", inpstr, &par);
   type1[lx] = inpstr[0] -'A' + 1;
   if(lx) to1[par].push_back(lx);
  }
  for(int lx =  0;lx < n2;lx++){
   scanf("%s %d", inpstr, &par);
   type2[lx] = inpstr[0] - 'A' + 1;
   if(lx) to2[par].push_back(lx);
  }
  gethash1(0); gethash2(0);
  printf("%d\n", res);
 }
 return 0;
}