正题

题目链接:https://www.luogu.com.cn/problem/P4323

题目大意

给出\(n\)个点的树和加上一个点之后的树（编号打乱）。

求多出来的是哪个点（如果有多少个就输出编号最小的）。

\(1\leq n\leq 10^5\)

解题思路

定义一下\(hash\)值\(P(i)\)

我的做法是\(P(i)=p^i\)，\(p\)是一个质数，当然这样好像容易被卡，安全点的做法是用第\(i\)个质数或者直接用复数\(hash\)。

然后定义一下带根的\(hash\)值

\[f_x=\sum_{y\in son_x}f_y\times P(siz_y)
\]

然后换根求出两棵树里面所有点作为根的\(hash\)值，第一棵树里的丢进\(map\)。然后第二棵树里面枚举一下叶子然后算一下去掉之后的\(hash\)值在\(map\)里面匹配（1号点要特判）

时间复杂度\(O(n\log n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#define ll long long

using namespace std;

const ll N=1e5+10,P=998244353,p=133331;

vector<ll> T[N],G[N];map<ll,bool>mp;

ll n,siz[N],pw[N],f[N],g[N];

ll power(ll x,ll b){

	ll ans=1;

	while(b){

		if(b&1)ans=ans*x%P;

		x=x*x%P;b>>=1;

	}

	return ans;

}

void Dfs1(ll x,ll fa,vector<ll> *T){

	siz[x]=f[x]=1;

	for(ll i=0;i<T[x].size();i++){

		ll y=T[x][i];

		if(y==fa)continue;

		Dfs1(y,x,T);siz[x]+=siz[y];

		(f[x]+=f[y]*pw[siz[y]]%P)%=P;

	}

	return;

}

void Dfs2(ll x,ll fa,vector<ll> *T){

	for(ll i=0;i<T[x].size();i++){

		ll y=T[x][i];

		if(y==fa)continue;

		g[y]=(g[x]-f[y]*pw[siz[y]]%P+P)%P;

		(g[y]=f[y]+g[y]*pw[siz[1]-siz[y]]%P)%=P;

		Dfs2(y,x,T);

	}

	return;

}

signed main()

{

	scanf("%lld",&n);pw[0]=1;

	for(ll i=1;i<=n+1;i++)

		pw[i]=pw[i-1]*p%P;

	for(ll i=1;i<n;i++){

		ll x,y;

		scanf("%lld%lld",&x,&y);

		G[x].push_back(y);

		G[y].push_back(x);

	}

	for(ll i=1;i<=n;i++){

		ll x,y;

		scanf("%lld%lld",&x,&y);

		T[x].push_back(y);

		T[y].push_back(x);

	}

	Dfs1(1,1,G);g[1]=f[1];Dfs2(1,1,G);

	for(ll i=1;i<=n;i++)mp[g[i]]=1;

	Dfs1(1,1,T);g[1]=f[1];

	Dfs2(1,1,T);

	if(T[1].size()<=1){

		ll y=T[1][0];

		if(mp[f[y]])

		{puts("1");return 0;}

	}

	for(ll x=2;x<=n+1;x++){

		if(T[x].size()>1)continue;

		ll y=T[x][0];

		ll tmp=(g[y]-pw[1]+P)%P;

		if(mp[tmp]){printf("%lld\n",x);return 0;}

	}

	return 0;

}

巴特西

P4323-[JSOI2016]独特的树叶【换根dp,树哈希】

正题

题目大意

解题思路

code

最新文章

热门文章