洛谷P15901题解

题目描述给定一棵包含 n 个结点的有根二叉树结点依次以 1,2,…,n 编号根结点编号为 1。对于结点 i其左儿子的编号记为 li​右儿子编号记为 ri​。特别地如果左儿子不存在则 li​0如果右儿子不存在则 ri​0。树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 n 棵子树中有多少棵子树是完全二叉树。输入格式第一行一个正整数 n表示有根二叉树结点数量。接下来 n 行每行两个正整数 li​,ri​表示结点 i 的左儿子编号和右儿子编号。输出格式输出一行一个整数表示所有子树中完全二叉树的数量。思路一道树形dp以一个节点为根树是完全二叉树左右结点为根的树 高度相同左结点为满二叉树右结点为完全二叉树 or 左完全右满#includebits/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].l0){ dfs(a[u].l,depth1); h[u]max(h[u],h[a[u].l]); } if(a[u].r0){ dfs(a[u].r,depth1); h[u]max(h[u],h[a[u].r]); } if (a[u].l0a[u].r0) dp[u]2; else if(a[u].r0h[a[u].l]depth1) dp[u]1; else if(h[a[u].l]h[a[u].r]){ if(dp[a[u].l]2dp[a[u].r]2) dp[u]2; else if(dp[a[u].l]2dp[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() { cinn; for (int i1;in;i){ cina[i].la[i].r; } dfs(1,0); coutans; }