题目链接:https://www.luogu.org/problemnew/show/P5018
嘛,这道题,其实理解要比同一套的题的上一道简单得多得多得多得多得多......,主要是把题读懂,明白要做什么就很简单了。
让我们先分析题目:
这道题要求树的结构和权值相同,举个栗子~如下图(编号为id),就要求2,3的权值相同,4,7的权值相同,5,6的权值相同(绝对不是简单的左节点和右节点相同,相信这很容易发现),而第二幅图就是典型的结构不对啦!
好了,明白了这些我们就明白了题意,居然只明白了题意,接下来我们就要看如何实现算法,我们可以先dfs一遍把每棵子树的大小size求出,然后每棵子树check一下,如果这棵子树满足要求,就更新ans。
那么问题就来了,n是10^6,每棵都枚举时间不会爆嘛???答案当然是不会,不然还干嘛讲这个,因为在check的时候一旦发现不满足条件了就return false,就节省了很多时间。如果还是有些不明白就看代码吧!代码可以说是非常容易理解了!
#include<bits/stdc++.h> #define N 1000002 using namespace std; int maxdep=0,tot=0; int v[N],son[N][3],size[N]; void dfs(int x) { size[x]=1; if(son[x][0]!=-1) { dfs(son[x][0]); size[x]+=size[son[x][0]]; } if(son[x][1]!=-1) { dfs(son[x][1]); size[x]+=size[son[x][1]]; } } int check(int a,int b) { if(a==-1&&b==-1) return 1;//到底了 if(a!=-1&&b!=-1&&v[a]==v[b]&&check(son[a][0],son[b][1])&&check(son[b][0],son[a][1])) return 1;//注意对称的特点 return 0; } int main() { // freopen("tree.in","r",stdin); // freopen("tree.out","w",stdout); int n,maxx=-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",&son[i][0],&son[i][1]); dfs(1); for(int i=1;i<=n;i++) if(check(son[i][0],son[i][1])) maxx=max(maxx,size[i]); printf("%d",maxx); } /* 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 */
结束撒花~