为什么我的hash正解,代码简洁,复杂度O(n)题解,管理员大佬不给我过呢?首先O(n)题解没几篇吧?hash没几篇吧?请管理员大佬仔细看看我的题解和哪一篇思路一样了?(
我的玄学翻转树hash啊)
我的第一道树哈希
背景:
此题可以说是我NOIP2018打的最漂亮的一道题
虽然时间复杂度O(n)可是我在i5的机子上跑出了3000ms+????
考完之后看整个江西赛区只有我一个人打出来了（
好开心,据说chen_zhe大佬当场都没有打出来）
之后来洛谷逛了一圈题解，没有看到我满意的。。。。不是编译出来一大堆警告就是时间复杂度太高，而且我的思路
貌似全国第一无二？
所以很抱歉时隔几个月才发表这一片题解QAQ，大家互相学习一下
我在考试时大便时间无师自通想出来的玄学树哈希
其实跑一边dfs就好了
原理：若一个树对称，那么将他的左子树翻转一遍（镜面成像差不多）将等于他的右子树，判断相等的方法就是哈希啦
求哈希也很简单，只要把他的左子树和右子树的哈希值哈希一下就是以当前节点为根的子树的哈希值，再一层一层递归上去就Ojbk了
至于翻转（
这么弱智的问题需要我说吗？），swap一下左子树和右子树的哈希值不就是了
最后献上我考试时打出来的代码（left数组撞上关键字加了一个下划线）
#include<bits/stdc++.h>
using namespace std;
int ans,dis[1000005],_left[1000005],_right[1000005],n;
int hash(int ha,int hb,int hc) {//玄学树哈希
ha*=13331;
ha%=INT_MAX;
ha+=hb;
ha%=INT_MAX;
ha*=13331;
ha%=INT_MAX;
ha+=hc;
ha%=INT_MAX;
ha*=13331;
ha%=INT_MAX;
return ha;
}
pair<long long,int> dfs(int t,bool CanIGo) {
//first存哈希值，second存树的子节点的个数
pair<int,int> QwQ;
if(t==-1) {
QwQ.first=1;
QwQ.second=0;
return QwQ;
}
pair<long long,int> l=dfs(_left[t],1);
pair<long long,int> r=dfs(_right[t],0);
if(CanIGo) swap(l,r);//CanIGo存当前节点是不是父节点的左子树，如果是就swap哈希值镜面成像（这一步最重要！！！）
QwQ.second=l.second+r.second+1;
if(l.first==r.first&&QwQ.second>ans) ans=QwQ.second;//更新值
QwQ.first=hash(l.first,r.first,dis[t]);
if(QwQ.first<=0) QwQ.first+=INT_MAX;
//防止溢出，考试的时候脑子不好使背不出来unsigned这个词哈哈哈
return QwQ;
}
int main() {
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",dis+i);
for(int i=1;i<=n;i++)
scanf("%d%d",_left+i,_right+i);
dfs(1,1);
cout<<ans<<endl;
return 0;
}
