对称二叉树(dfs+哈希)

题目：

给一棵以为根，带点权的二叉树。让你找出一棵最大的子树是对称二叉树。对称二叉树就是将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。

做法：

所谓对称二叉树我们转换一下概念就是子树的中根遍历序列是一个回文，当然要保证树的形态一致，我们在对树进行中序遍历时，进入一个结点就加一个，退出一个结点就加一个。然后我们对中序遍历序列正反都做一个哈希，在反序列中和进行互换。然后我们就能在时间复杂度判断一段区间是否是回文序列了。此时，我们枚举每棵子树对应的区间序列，判断一下就行。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(void){
    char ch = getchar();
    int ans = 0, f = 1;
    while (!isdigit(ch)){if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) ans = ans*10 + ch-'0', ch = getchar();
    return ans*f;
}
const int N = 1e6 + 7;
const ull seed = 131;
struct node{
    int l, r, val, sze;
}T[N];
int n, tot, tag[3*N], from[N], to[N];
ull h1[3*N], h2[3*N], bas[3*N];
void dfs(int u){
    T[u].sze = 1;
    tag[++tot] = '('; from[u] = tot;
    if (T[u].l != -1) dfs(T[u].l), T[u].sze += T[T[u].l].sze;
    tag[++tot] = T[u].val;
    if (T[u].r != -1) dfs(T[u].r), T[u].sze += T[T[u].r].sze;
    tag[++tot] = ')'; to[u] = tot;
}
int get1(int l, int r){
    return h1[r]-h1[l-1]*bas[r-l+1];
}
int get2(int l, int r){
    int ll = tot-r+1, rr = tot-l+1;
    return h2[rr]-h2[ll-1]*bas[rr-ll+1];
}
int main(void){
    n = read();
    for (int i = 1; i <= n; ++i) T[i].val = read();
    for (int i = 1;  i<= n; ++i) T[i].l = read(), T[i].r = read();
    dfs(1);
    for (int i = bas[0] = 1; i <= tot; ++i){
        bas[i] = bas[i-1]*seed;
        int x = tag[i];
        h1[i] = h1[i-1]*seed+x;
        int y = tag[tot-i+1];
        if (y == '(')  y = ')';
        else if (y == ')') y = '(';
        h2[i] = h2[i-1]*seed+y;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i){
        if (get1(from[i], to[i]) == get2(from[i], to[i])) ans = max(ans, T[i].sze);
    }
    printf("%d\n", ans);
    return 0;
}