@[老K](/space/show?uid=8943) QAQ（所以这题从看上去很神的题目变成了一个相对简单的dfs题目？）
by chen_zhe @ 2018-11-15 22:09:18
@[chen_zhe](/space/show?uid=8457) 这题数据是真的水，我把左子树或右子树不是对称二叉树（其实不然）的节点剪掉了都能拿76分，[记录](https://www.luogu.org/record/show?rid=13793249)，别的民间数据只有40
by 7KByte @ 2018-11-15 22:14:40
表示递归一次满。。。
#include <iostream>
#include <fstream>
using namespace std;
int _n;
int _tree[1000010];
int _left[1000010];
int _right[1000010];
int _res = 0;
bool ReverseEqual(int left, int right){
if (left==-1 && right==-1) {
return true;
}
if (left==-1 || right==-1) {
return false;
}
if (_tree[left]!=_tree[right]) {
return false;
}
return ReverseEqual(_left[left],_right[right])&&ReverseEqual(_left[right],_right[left]);
}
bool Check(int root) {
return ReverseEqual(_left[root],_right[root]);
}
int Count(int root) {
if (root==-1) {
return 0;
}
return 1+Count(_left[root])+Count(_right[root]);
}
int main(){
cin >> _n;
for (int i = 1; i<_n+1; i++) {
cin >> _tree[i];
}
for (int i = 1; i<_n+1; i++) {
cin >> _left[i] >> _right[i];
}
for (int i = 1; i<_n+1; i++) {
if (Check(i)){
_res = max(_res,Count(i));
}
}
cout << _res << endl;
return 0;
}
by lcyxds @ 2018-11-15 22:59:43
#include <iostream>
#include <fstream>
using namespace std;
int _n;
int _tree[1000010];
int _left[1000010];
int _right[1000010];
int _res = 0;
bool ReverseEqual(int left, int right){
if (left==-1 && right==-1) {
return true;
}
if (left==-1 || right==-1) {
return false;
}
if (_tree[left]!=_tree[right]) {
return false;
}
return ReverseEqual(_left[left],_right[right])&&ReverseEqual(_left[right],_right[left]);
}
bool Check(int root) {
return ReverseEqual(_left[root],_right[root]);
}
int Count(int root) {
if (root==-1) {
return 0;
}
return 1+Count(_left[root])+Count(_right[root]);
}
int main(){
cin >> _n;
for (int i = 1; i<_n+1; i++) {
cin >> _tree[i];
}
for (int i = 1; i<_n+1; i++) {
cin >> _left[i] >> _right[i];
}
for (int i = 1; i<_n+1; i++) {
if (Check(i)){
_res = max(_res,Count(i));
}
}
cout << _res << endl;
return 0;
}
by lcyxds @ 2018-11-15 23:00:01
比赛的时候我看了看第三个数据，不到0.5秒，轻信不会爆T，果然就没爆
by lcyxds @ 2018-11-15 23:01:32
@[chen_zhe](/space/show?uid=8457) 这题实际上是信仰题？？？？
by 老K @ 2018-11-15 23:09:02
加上快读快写优化的dfs+剪枝的59行程序成功考场AC
by zxy2004 @ 2018-11-20 19:58:49
考古+upd：
当时考场上我连算法复杂度是什么都不知道（
现在看来这个应该是 $O(nlogn)$ 的，单次询问最坏 $O(n)$ ，但是 Check 函数复杂度依赖于左右子树中较小的那一个，而 Count 函数复杂度是子树大小，且只统计对称二叉树，总复杂度应该都是 $O(nlogn)$，（类似于启发式合并的想法？
不知道这个代码是否会被 Hack，$n$ 有 $1e6$ 而且常数并不小
by lcyxds @ 2021-03-26 22:11:41