洛谷P15901题解

题目描述

给定一棵包含 n 个结点的有根二叉树，结点依次以 1,2,…,n 编号，根结点编号为 1。

对于结点 i，其左儿子的编号记为 li​，右儿子编号记为 ri​。特别地，如果左儿子不存在则 li​=0，如果右儿子不存在则 ri​=0。

树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 n 棵子树中，有多少棵子树是完全二叉树。

输入格式

第一行，一个正整数 n，表示有根二叉树结点数量。

接下来 n 行，每行两个正整数 li​,ri​，表示结点 i 的左儿子编号和右儿子编号。

输出格式

输出一行，一个整数，表示所有子树中完全二叉树的数量。

思路

一道树形dp

以一个节点为根树是完全二叉树：左右结点为根的树 高度相同&&左结点为满二叉树&&右结点为完全二叉树 or 左完全&&右满

#include<bits/stdc++.h> using namespace std; #define N 100005 #define int long long struct node{ int l,r; }; node a[N]; int dp[N],h[N]; int ans,n; void dfs(int u,int depth){ h[u]=depth; if (a[u].l>0){ dfs(a[u].l,depth+1); h[u]=max(h[u],h[a[u].l]); } if(a[u].r>0){ dfs(a[u].r,depth+1); h[u]=max(h[u],h[a[u].r]); } if (a[u].l==0&&a[u].r==0) dp[u]=2; else if(a[u].r==0&&h[a[u].l]==depth+1) dp[u]=1; else if(h[a[u].l]==h[a[u].r]){ if(dp[a[u].l]==2&&dp[a[u].r]==2) dp[u]=2; else if(dp[a[u].l]==2&&dp[a[u].r]==1) dp[u]=1; } else if(h[a[u].l]==h[a[u].r]+1) { if((dp[a[u].l]==1||dp[a[u].l]==2)&&dp[a[u].r]==2) dp[u]=1; } ans+=(dp[u]>0); } signed main() { cin>>n; for (int i=1;i<=n;i++){ cin>>a[i].l>>a[i].r; } dfs(1,0); cout<<ans; }