NC20230. [JSOI2016]独特的树叶
描述
输入描述
输入一行包含一个正整数N。
接下来N-1行，描述树A，每行包含两个整数表示树A中的一条边；
接下来N行，描述树B，每行包含两个整数表示树B中的一条边。
输出描述
输出一行一个整数，表示树B中相比树A多余的那个叶子的编号。
如果有多个符合要求的叶子，输出B中编号最小的那一个的编号
示例1
输入:
5 1 2 2 3 1 4 1 5 1 2 2 3 3 4 4 5 3 6
输出:
1
C++(g++ 7.5.0) 解法, 执行用时: 175ms, 内存消耗: 22212K, 提交时间: 2023-05-23 21:13:03
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
const int maxn=100005;
const unsigned long long seed_one=998244353;
const unsigned long long seed_two=100000007;
struct Hash
{
unsigned long long P,Q;
void operator = (const Hash & B)
{
P=B.P;Q=B.Q;
}
Hash operator ^ (const Hash & B) const
{
Hash A;
A.P=P^B.P; A.Q=Q^B.Q;
return A;
}
Hash operator * (const unsigned long long & B) const
{
Hash A;
A.P=P*B; A.Q=Q*B;
return A;
}
Hash operator + (const unsigned long long & B) const
{
Hash A;
A.P=P+B; A.Q=Q+B;
return A;
}
Hash operator - (const unsigned long long & B) const
{
Hash A;
A.P=P-B; A.Q=Q-B;
return A;
}
bool operator < (const Hash & B) const
{
return P<B.P || P==B.P && Q<B.Q;
}
Hash complicated(int S) const
{
Hash O;
O.P=P*seed_one+S;
O.Q=Q*seed_two+S;
return O;
}
}fA[maxn],fB[maxn],temp,Hash_rootA[maxn],Hash_rootB[maxn];
vector<int> A[maxn],B[maxn];
int n,x,y,sizeA[maxn],sizeB[maxn];
set <Hash> S;
void dfsA(int u,int father)
{
sizeA[u]=1;
for (int i=0,N=A[u].size();i<N;++i)
{
int v=A[u][i];
if (v==father) continue;
dfsA(v,u);
fA[u]=((fA[u])^(fA[v].complicated(sizeA[v])));
sizeA[u]+=sizeA[v];
}
fA[u]=fA[u]+233*sizeA[u]+1;
}
void re_dfsA(int u,int father)
{
if (father==0) Hash_rootA[u]=fA[u];
else
{
temp=((Hash_rootA[father]-233*n-1)^fA[u].complicated(sizeA[u]));
temp=(temp+233*(n-sizeA[u])+1);
Hash_rootA[u]=((fA[u]-233*sizeA[u]-1)^temp.complicated(n-sizeA[u]));
Hash_rootA[u]=Hash_rootA[u]+233*n+1;
}
for (int i=0,N=A[u].size();i<N;++i)
{
int v=A[u][i];
if (v==father) continue;
re_dfsA(v,u);
}
}
void dfsB(int u,int father)
{
sizeB[u]=1;
for (int i=0,N=B[u].size();i<N;++i)
{
int v=B[u][i];
if (v==father) continue;
dfsB(v,u);
fB[u]=(fB[u]^(fB[v].complicated(sizeB[v])));
sizeB[u]+=sizeB[v];
}
fB[u]=fB[u]+233*sizeB[u]+1;
}
void re_dfsB(int u,int father)
{
if (father==0) Hash_rootB[u]=fB[u];
else
{
temp=(Hash_rootB[father]-233*(n+1)-1)^fB[u].complicated(sizeB[u]);
temp=(temp+233*(n+1-sizeB[u])+1);
Hash_rootB[u]=((fB[u]-233*sizeB[u]-1)^temp.complicated(n+1-sizeB[u]));
Hash_rootB[u]=Hash_rootB[u]+233*(n+1)+1;
}
for (int i=0,N=B[u].size();i<N;++i)
{
int v=B[u][i];
if (v==father) continue;
re_dfsB(v,u);
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
A[x].push_back(y);
A[y].push_back(x);
}
for (int i=1;i<=n;++i)
{
scanf("%d%d",&x,&y);
B[x].push_back(y);
B[y].push_back(x);
}
dfsA(1,0);
re_dfsA(1,0);
dfsB(1,0);
re_dfsB(1,0);
for (int i=1;i<=n;++i)
S.insert(Hash_rootA[i]);
//for (int i=1;i<=n+1;++i) cout<<i<<' '<<Hash_rootA[i].P<<' '<<Hash_rootA[i].Q<<' '<<Hash_rootB[i].P<<' '<<Hash_rootB[i].Q<<endl;
for (int i=1;i<=n+1;++i)
if (B[i].size()==1)
{
Hash T;
T.P=T.Q=234;
Hash temp=((Hash_rootB[B[i][0]]-233*(n+1)-1)^T.complicated(1));
temp=(temp+233*n+1);
// cout<<i<<' '<<temp.P<<' '<<temp.Q<<endl;
if (S.find(temp)!=S.end())
{
printf("%d\n",i);
break;
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 83ms, 内存消耗: 12644K, 提交时间: 2020-03-26 20:18:28
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define fgx cerr<<"------------------"<<endl;
#define dgx cerr<<"=================="<<endl;
#define prt(x) cerr<<#x<<": "<<x<<endl;
inline int read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int MAXN = 100010; //H[j]*Seed+Sz[j]
const ULL Base = 1000000007;
int N; map<ULL,bool> mp;
struct tree{
int Node[MAXN<<1],Next[MAXN<<1],Root[MAXN]; int cnte;
int Deg[MAXN],sz[MAXN]; int opN; ULL f[MAXN],g[MAXN];;
inline ULL Data(ULL x,ULL y){ return x*Base+y; }
inline void insert(int x,int y){
Node[++cnte]=y; Next[cnte]=Root[x]; Root[x]=cnte;
Node[++cnte]=x; Next[cnte]=Root[y]; Root[y]=cnte;
++Deg[x]; ++Deg[y];
} inline void dfs1(int x,int Fa){
sz[x]=1; g[x]=1;
for(int i=Root[x];i;i=Next[i]){
int y=Node[i];
if(y!=Fa){
dfs1(y,x); sz[x]+=sz[y]; g[x]^=Data(g[y],sz[y]);
}
}
} inline void dfs2(int x,int Fa){
if(!Fa)f[x]=g[x]; else f[x]=g[x]^Data(f[Fa]^Data(g[x],sz[x]),opN-sz[x]);
for(int i=Root[x];i;i=Next[i]){ int y=Node[i]; if(y!=Fa) dfs2(y,x); }
} inline bool isLev(int x){ return Deg[x]==1; }
inline ULL Nowk(int x){
int Fa=Node[Root[x]];
return f[Fa]^Data(g[x],1);
}
}A,B;
int main(){
N=read(); A.opN=N; B.opN=N+1;
for(int i=1;i<N;i++){
int x=read(),y=read();
A.insert(x,y);
} A.dfs1(1,0); A.dfs2(1,0);
for(int i=1;i<=N;i++) mp[A.f[i]]=true;
for(int i=1;i<=N;i++){
int x=read(),y=read();
B.insert(x,y);
} for(int i=1;i<=N+1;i++)
if(!B.isLev(i)){
B.dfs1(i,0); B.dfs2(i,0); break;
}
for(int i=1;i<=N+1;i++)
if(B.isLev(i)){
ULL now=B.Nowk(i);
if(mp[now]){
printf("%d\n",i); return 0;
}
}
return 0;
}