标签：DNA cur int len 20 树形 n1 300005
- 由于左右子树不等价，我们可以以Trie树的视角考察原树，发现“叶子节点不超过20个”的条件等价于这棵Trie树可以用不超过20个01字符串表示
- 树的匹配不好做，但字符串匹配是可做的。于是我们可以想到把树的匹配“折叠”成20个字符串的匹配
- 猜想时间复杂度是O(20n），其中20是枚举的复杂度
- 把字符串放入dfs的参数中会导致奇怪的问题
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int P=131;
int l[2][300005],r[2][300005],f[300005][20];
int t[25];
unsigned long long h[25],p[300005],val;
unsigned long long cur[300005];
int cnt[300005];
vector<int>ans;
int n,tot;
void pre()
{
for(int j=1;j<=18;j++)
{
for(int i=1;i<=n;i++)
{
if(f[i][j-1]!=-1)
{
f[i][j]=f[f[i][j-1]][j-1];
}
else
{
f[i][j]=-1;
}
}
}
}
void dfs1(int n1,int len)
{
if(!l[1][n1]&&!r[1][n1])
{
tot++;
t[tot]=len;
h[tot]=val;
return;
}
if(l[1][n1])
{
unsigned long long tmp=val;
val=val*P+1;
dfs1(l[1][n1],len+1);
val=tmp;
}
if(r[1][n1])
{
unsigned long long tmp=val;
val=val*P+2;
dfs1(r[1][n1],len+1);
val=tmp;
}
}
int get(int n1,int k)
{
for(int i=18;i>=0;i--)
{
if(((k>>i)&1)==1)
{
n1=f[n1][i];
}
}
return n1;
}
void dfs2(int n1,int len)
{
for(int i=1;i<=tot;i++)
{
if(len>=t[i])
{
int r=len;
int l=len-t[i];
if(cur[r]-cur[l]*p[t[i]]==h[i])
{
cnt[get(n1,t[i])]++;
}
}
}
len++;
if(l[0][n1])
{
cur[len]=cur[len-1]*P+1;
dfs2(l[0][n1],len);
}
if(r[0][n1])
{
cur[len]=cur[len-1]*P+2;
dfs2(r[0][n1],len);
}
len--;
if(cnt[n1]==tot)
{
ans.push_back(n1);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
p[0]=1;
for(int i=1;i<=300000;i++)
{
p[i]=p[i-1]*P;
}
int T;
cin>>T;
while(T--)
{
cin>>n;
f[0][0]=-1;
for(int i=0;i<n;i++)
{
cnt[i]=0;
cin>>l[0][i]>>r[0][i];
if(l[0][i])
{
f[l[0][i]][0]=i;
}
if(r[0][i])
{
f[r[0][i]][0]=i;
}
}
pre();
int m;
cin>>m;
for(int i=0;i<m;i++)
{
cin>>l[1][i]>>r[1][i];
}
tot=0;
dfs1(0,0);
ans.clear();
dfs2(0,0);
cout<<ans.size()<<endl;
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)
{
if(i!=0)
{
cout<<" ";
}
cout<<ans[i];
}
cout<<endl;
}
return 0;
}
标签：DNA,
cur,
int,
len,
20,
树形,
n1,
300005
From： https://www.cnblogs.com/watersail/p/18385466