正題

題目鏈接:https://www.luogu.com.cn/problem/P4323

---

題目大意

給出$n$個點的樹和加上一個點之后的樹（編號打亂）。

求多出來的是哪個點（如果有多少個就輸出編號最小的）。

$1\le n\le 10^5$

---

解題思路

定義一下$hash$值$P(i)$

我的做法是$P(i)=p^i$，$p$是一個質(zhì)數(shù)，當(dāng)然這樣好像容易被卡，安全點的做法是用第$i$個質(zhì)數(shù)或者直接用復(fù)數(shù)$hash$。

然后定義一下帶根的$hash$值
$$f_x=\sum _{y\in so{n}_x}{f}_y\times P(si{z}_y)$$

然后換根求出兩棵樹里面所有點作為根的$hash$值，第一棵樹里的丟進(jìn)$map$。然后第二棵樹里面枚舉一下葉子然后算一下去掉之后的$hash$值在$map$里面匹配（1號點要特判）

時間復(fù)雜度$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; }

總結(jié)

以上是生活随笔為你收集整理的P4323-[JSOI2016]独特的树叶【换根dp,树哈希】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。