Luogu p5018 [noip2018 popularization group] symmetric binary tree problem solution

Luogu P5018 [NOIP2018 Popularization group ] Symmetric binary tree Answer key

Topic link ：P5018 [NOIP2018 Popularization group ] Symmetric binary tree

The question ：

If a rooted tree with some weight meets the following conditions , Is called symmetric binary tree by Xuanxuan ：

1. Binary tree ;
2. Swap the left and right subtrees of all nodes of this tree , The structure of the corresponding position of the new tree and the original tree is the same and the point weight is equal .

The number in the node in the figure below is the weight , Out of node $id$ Indicates the node number .

Now give a binary tree , I hope you find a subtree of it , The subtree is a symmetric binary tree , And the number of nodes most . Please output the number of nodes of this subtree .

Be careful ： A tree with only its roots is also a symmetric binary tree . It is agreed in this question , To the node $T$ A tree that is the root of a child tree “ Son Trees ” refer to ： node $T$ And all its descendant nodes .

【 Data scale and agreement 】
common $25$ A test point .
$v_i\le 1000$.
Test point $1\sim 3,n\le 10$, Ensure that all nodes of the left subtree of the root node have no right children , Right of root node All nodes of the subtree have no left children .
Test point $4\sim 8,n\le 10$.
Test point $9\sim 12,n\le 10^5$, Ensure that the input is a “ Full binary tree ” .
Test point $13\sim 16,n\le 10^5$, Ensure that the input is a “ Perfect binary tree ”.
Test point $17\sim 20,n\le 10^5$, Ensure that the point weight of the input tree is $1$.
Test point $21\sim 25,n\le 10^6$.

For every point of direct violence dfs Its left and right subtrees can be judged

Pay attention to the direction of symmetry and don't write it wrong

Time complexity $O(n\log n)$

Why won't the chain get stuck , Because the intermediate judgment is equivalent to pruning off

Only the complete binary tree will arrive $O(n\log n)$

Code ：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e6+15)

int n,ch[N][2],val[N],sz[N];
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
void dfs(int u)
{
    
    sz[u]=1;
    if(ls(u)!=-1)
    {
    
        dfs(ls(u));
        sz[u]+=sz[ls(u)];
    }
    if(rs(u)!=-1)
    {
    
        dfs(rs(u));
        sz[u]+=sz[rs(u)];
    }
}
bool solve(int u,int v)
{
    
    if(u==-1&&v==-1)return 1;
    if(u==-1||v==-1)return 0;
    return val[u]==val[v]&&solve(ls(u),rs(v))&&solve(rs(u),ls(v));
}
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> val[i];
    for(int i=1; i<=n; i++)
        cin >> ls(i) >> rs(i);
    dfs(1);
    int ans=0;
    for(int i=1; i<=n; i++)
        if(solve(ls(i),rs(i)))
            ans=max(ans,sz[i]);
    cout << ans << '\n';
    return 0;
}

Reprint please explain the source