1 solutions
-
1
#include<iostream> #include<cstdio> #include<vector> #include<map> using namespace std; const int NR=1e5+10,P=1e5+7,A=1; //A是单点点权 unsigned long long p[NR]; struct Tree { vector<int> e[NR]; int n,sz[NR]; unsigned long long g[NR],h[NR]; void dfs(const int x,const int fa) //求sz[i]、h[i] { sz[x]=1; h[x]=A; int i; for(i=0;i<e[x].size();i++) { int y=e[x][i]; if(y!=fa) { dfs(y,x); sz[x]+=sz[y]; h[x]+=h[y]*p[sz[y]]; } } return; } void cal(const int x,const int fa) { int i; for(i=0;i<e[x].size();i++) { int y=e[x][i]; if(y!=fa) { g[y]=h[y]+(g[x]-h[y]*p[sz[y]])*p[n-sz[y]]; cal(y,x); } } return; } }; map<unsigned long long,bool> mp; Tree a,b; int main() { int i; cin>>a.n; b.n=a.n+1; p[0]=1; for(i=1;i<=b.n;i++) p[i]=p[i-1]*P; //要求到n+1 // for(i=1;i<=b.n;i++) cout<<p[i]<<" "; // cout<<endl; for(i=1;i<a.n;i++) { int x,y; cin>>x>>y; a.e[x].push_back(y); a.e[y].push_back(x); } for(i=1;i<b.n;i++) { int x,y; cin>>x>>y; b.e[x].push_back(y); b.e[y].push_back(x); } //先求出A的n个hash值 a.dfs(1,0); a.g[1]=a.h[1]; a.cal(1,0); // for(i=1;i<=a.n;i++) cout<<a.g[i]<<" "; // cout<<endl; //再求出B的n+1个hash值 b.dfs(1,0); b.g[1]=b.h[1]; b.cal(1,0); for(i=1;i<=a.n;i++) mp[a.g[i]]=true; for(i=1;i<=b.n;i++) { if(b.e[i].size()!=1) continue; //i不是叶子就跳过 int y=b.e[i][0]; //找到i点唯一邻居 if(mp[b.g[y]-A*P]) //y作为根然后去掉i点 { cout<<i; break; } } return 0; }
- 1
Information
- ID
- 3272
- Time
- 1000ms
- Memory
- 512MiB
- Difficulty
- 6
- Tags
- # Submissions
- 1
- Accepted
- 1
- Uploaded By