%%%dalao Orz
大佬太强了
by Breeze_qf @ 2019-11-13 07:56:09
%%%实测Manacher能过
by Schwarzkopf_Henkal @ 2019-11-13 07:57:25
**%%% tql tql**
by wick @ 2019-11-13 07:59:36
@[Schwarzkopf_Henkal](/user/251723) 求助Manacher怎么判断树的形状
by bellmanford @ 2019-11-13 08:07:29
@[初音美如画](/user/207667) 你这样好象是错的，一棵对称树的子节点不一定也是
像这组
```
5
1 1 1 1 1
2 3
4 -1
-1 5
-1 -1
-1 -1
```
by bellmanford @ 2019-11-13 08:18:23
@[bellmanford](/user/116015) 啊，我知道了，谢谢
by 昨日之日 @ 2019-11-13 08:29:44
@[bellmanford](/user/116015) 两个节点相同当且仅当他们的值和层次都相同，对树进行中序遍历把树拍扁，对于一个对称中心，要是该点的对称半径不等于该点的左孩子数，或者左孩子数不等于右孩子数，更新r和对应的mid但将该点的对称半径置为0.
by Schwarzkopf_Henkal @ 2019-11-13 08:30:42
```cpp
for(int i=1;i<=top;i++){
if(i<=r)
len[i]=min(len[mid*2-i],r-i);
while(man[i+len[i]+1].lvl==man[i-len[i]-1].lvl&&man[i+len[i]+1].v==man[i-len[i]-1].v)
len[i]++;
if(len[i]+i>r){
r=len[i]+i;
mid=i;
}//翻转是没有问题的.
if(len[i]!=man[i].lsc||man[i].lsc!=man[i].rsc)
len[i]=0;
ans=max(ans,len[i]*2+1);
}
```
@[bellmanford](/user/116015) 这是manacher部分的代码
by Schwarzkopf_Henkal @ 2019-11-13 08:32:06
@[Schwarzkopf_Henkal](/user/251723) 我就是这样做的，然而没过
你这样好像并没有判断树的形状啊
只判断了值和层次，没有判断左右儿子
by bellmanford @ 2019-11-13 08:34:55
@[Schwarzkopf_Henkal](/user/251723) 帮我看看呗
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
const int M=1e6+5;
int n,tot=0,ans=1,a[M],hw[M],val[M],pre[M];
char s[M];
struct Tree{
int ls,rs,size;
}tr[M];
int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') y=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
if(x*y==-1) return 0;
return x*y;
}
void manacher(){
int maxright=0,mid;
for(int i=1;i<=tot;i++){
if(i<maxright){
hw[i]=min(hw[(mid<<1)-i],hw[mid]+mid-i);
if(tr[tr[pre[i]].ls].size==tr[tr[pre[i]].rs].size&&hw[i]*2+1>=tr[pre[i]].size) ans=max(ans,tr[pre[i]].size);
}
else hw[i]=0;
while(a[i+hw[i]+1]==a[i-hw[i]-1]){
++hw[i];
if(tr[tr[pre[i]].ls].size==tr[tr[pre[i]].rs].size&&hw[i]*2+1>=tr[pre[i]].size) ans=max(ans,tr[pre[i]].size);
}
if(hw[i]+i>maxright){
maxright=hw[i]+i;
mid=i;
}
}
}
void dfs(int u){
if(u==0) return ;
tr[u].size=1;
dfs(tr[u].ls);
a[++tot]=val[u];
pre[tot]=u;
dfs(tr[u].rs);
tr[u].size+=(tr[tr[u].ls].size+tr[tr[u].rs].size);
}
int main(){
n=read();
for(int i=1;i<=n;i++) val[i]=read();
for(int i=1;i<=n;i++) tr[i].ls=read(),tr[i].rs=read();
dfs(1);
manacher();
// for(int i=1;i<=tot;i++) printf("%d ",a[i]);
// printf("\n");
// for(int i=1;i<=tot;i++) printf("%d ",pre[i]);
// printf("\n");
// for(int i=1;i<=tot;i++) printf("%d ",hw[i]);
// printf("\n");
printf("%d\n",ans);
}
```
by bellmanford @ 2019-11-13 08:36:34