題目描述###

一棵有點權的有根樹如果滿足以下條件，則被軒軒稱為對稱二叉樹：

• 二叉樹；
• 將這棵樹所有節點的左右子樹交換，新樹和原樹對應位置的結構相同且點權相等。

下圖中節點內的數字為權值，節點外的 id 表示節點編號。

現在給出一棵二叉樹，希望你找出它的一棵子樹，該子樹為對稱二叉樹，且節點數最多。請輸出這棵子樹的節點數。
注意：只有樹根的樹也是對稱二叉樹。本題中約定，以節點 T 為子樹根的一棵“子樹”指的是：節點 T 和它的全部后代節點構成的二叉樹。

輸入###

第一行一個正整數 n，表示給定的樹的節點的數目，規定節點編號 1~n，其中節點1 是樹根。
第二行 n 個正整數，用一個空格分隔，第 i 個正整數 vi 代表節點 i 的權值。
接下來 n 行，每行兩個正整數 li , ri ，分別表示節點 i 的左右孩子的編號。如果不存在左 / 右孩子，則以 ?1 表示。兩個數之間用一個空格隔開。

輸出###

輸出共一行，包含一個整數，表示給定的樹的最大對稱二叉子樹的節點數。
輸入樣例 1
2
1 3
2 -1
-1 -1
輸入樣例 2
10
2 2 5 5 5 5 4 4 2 3
9 10
-1 -1
-1 -1
-1 -1
-1 -1
-1 2
3 4
5 6
-1 -1
7 8
輸出樣例 1
1
輸出樣例 2
3

輸入輸出樣例 1 說明

最大的對稱二叉子樹為以節點 2 為樹根的子樹，節點數為 1。

輸入輸出樣例 2 說明

最大的對稱二叉子樹為以節點 7 為樹根的子樹，節點數為 3。

數據規模與約定###

共25個測試點。vi≤1000
測試點1~3，n≤10,保證根結點的左子樹的所有節點都沒有右孩子，根結點的右子樹的所有節點都沒有左孩子。
測試點4~8，n≤10。
測試點9~12，n≤10^5,保證輸入是一棵“滿二叉樹”。
測試點13~16，n≤10^5,保證輸入是一棵“完全二叉樹”。
測試點17~20，n≤10^5,保證輸入的樹的點權均為 1。
測試點21~25，n≤10^6。

解題思路###

這道題看起來難度很大，很多同學不敢去做。但實際上改題的做法很暴力：枚舉每個結點，如果它左右子樹大小相同，則暴力 Check 一下以這個結點為根的子樹是否合法。
雖然看上去很暴力（復雜度好像是O(n^2)），但實際上這樣做的時間復雜度的確是 O(nlog n)。
證明思路可以采用啟發式合并的時間復雜度證明思路。
即：因為左右子樹相同時才 check，因此每一次 check 樹的大小至少增大一倍。最多 log 次樹的大小就會到達 n，所以每個結點只會被 check log 次。
參考代碼

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1000000;
int siz[MAXN + 5], le[MAXN + 5], ri[MAXN + 5], v[MAXN + 5], ans;

bool check(int r1, int r2) {
	if( v[r1] != v[r2] ) return false;
	else if( r1 == 0 && r2 == 0 ) return true;
	else return check(le[r1], ri[r2]) && check(ri[r1], le[r2]);
}
int dfs1(int rt) {
	if( !rt ) return 0;
	else return siz[rt] = dfs1(le[rt]) + dfs1(ri[rt]) + 1;
}
void dfs2(int rt) {
	if( !rt ) return ;
	if( siz[le[rt]] == siz[ri[rt]] )
		if( check(le[rt], ri[rt]) ) ans = max(ans, siz[rt]);
	dfs2(le[rt]), dfs2(ri[rt]);
}
int main() 
{
	int n; v[0] = -1;
	scanf("%d", &n);
	for(int i=1;i<=n;i++)
		scanf("%d", &v[i]);
	for(int i=1;i<=n;i++) {
		scanf("%d%d", &le[i], &ri[i]);
		if( le[i] == -1 ) le[i] = 0;
		if( ri[i] == -1 ) ri[i] = 0;
	}
	dfs1(1);
	dfs2(1);
	printf("%d\n", ans);
	return 0;
}

解題思路2：###

如果一棵子樹是對稱的，那么他的中序變量和逆中序遍歷是相同的，也就是子樹的DFS序是回文串。
需要注意的是，不同層次結點是值有可能相同，這樣兒子在左邊或者右邊就判斷不出來（父親結點的值跟兒子一樣），因此，我們可以給結點的值加入層次，如加上層次*1001（超過權值的范圍）。
處理好DFS序和子樹結點數量后，跑一遍Manacher匹配最大回文串，如果回文長度跟子樹結點數量相等，那么就是對稱子樹，記錄最大值。
還有其他做法：哈希（有沖突怎么辦？）、爆搜（怎么剪枝？）
實現代碼：略。