中序遍历+马拉车
by 天朝理科生 @ 2019-05-04 18:08:51
@[天朝理科生](/space/show?uid=136321) 中序相同不等于同构啊
by SSerxhs @ 2019-05-04 18:18:43
@[SSerxhs](/space/show?uid=29826) 样例唬住我了。。。
不过我把每个中序的值都加上深度就水过了……
玄学
by 天朝理科生 @ 2019-05-04 18:22:54
@[SSerxhs](/space/show?uid=29826) 刚才看了 @[Cheng_yf](/space/show?uid=87691) 的题解，他的做法也是中序遍历和manacher，我发现我没有判断结构对称，然后挂在这了。
by 天朝理科生 @ 2019-05-04 18:34:14
再开一个数组记录深度的中序遍历结果，用这个深度数组和权值数组同时进行manacher就行了哦。
```cpp
/*正解*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
inline int read(){
int an=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){an=(an<<1)+(an<<3)+c-'0';c=getchar();}
return an*f;
}
const int N=1000010;
int n,w[N],a[N],b[N],lson[N],rson[N],tot,dfn[N],size[N],mx,id,r[N],ans;
void dfs(int x,int dp){
size[x]=1;
if(lson[x]!=-1){
dfs(lson[x],dp+1);
size[x]+=size[lson[x]];
}
dfn[++tot]=x;
a[tot]=w[x];
b[tot]=dp;
if(rson[x]!=-1){
dfs(rson[x],dp+1);
size[x]+=size[rson[x]];
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read();
for(int i=1;i<=n;i++)w[i]=read();
for(int i=1;i<=n;i++){
lson[i]=read();
rson[i]=read();
}
dfs(1,1);
for(int i=1;i<=n;i++){
if(mx>i)r[i]=min(r[2*id-i],mx-i);
while(i-r[i]>=1&&i+r[i]<=n&&a[i-r[i]]==a[i+r[i]]&&b[i-r[i]]==b[i+r[i]])r[i]++;
if(mx<i+r[i]){
mx=i+r[i];
id=i;
}
}
for(int i=1;i<=n;i++)
if(2*r[i]==size[dfn[i]]+1)
ans=max(ans,size[dfn[i]]);
printf("%d",ans);
return 0;
}
```
by 天朝理科生 @ 2019-05-04 18:41:44
@[天朝理科生](/space/show?uid=136321) 中序的时候和把深度和权值hash就好了
by SSerxhs @ 2019-05-04 22:47:18