今天在一本通上做题,做到NOIP2018的这道题,于是写出了以下代码:
#include<bits/stdc++.h>
using namespace std;
/*2024/7/28*/
const int maxn=1e6+10;
int n,num,ans,x,y,root=1;
struct node{
int val,lch,rch,size;
}tree[maxn];
bool flag[maxn];
inline char gc(){
static char buf[1<<16],*p1=buf,*p2=buf;
if(p1==p2)p2=(p1=buf)+fread(buf,1,1<<16,stdin);if(p1==p2)return EOF;
return *p1++;
}
template<typename _Tp>
inline void fastread(_Tp &x){
x=0;char c=gc();
while(!isdigit(c))c=gc();
while(isdigit(c))x=x*10-48+c,c=gc();
return;
}
inline int npsize(int x){
if(!x)return x;
tree[x].size=npsize(tree[x].lch)+npsize(tree[x].rch)+1;
if(tree[tree[x].lch].size!=tree[tree[x].rch].size)flag[x]=true;
return tree[x].size;
}
inline void npval(int x){
if(x==0)return;
npval(tree[x].lch);npval(tree[x].rch);
if(tree[tree[x].lch].val!=tree[tree[x].rch].val)flag[x]=true;
return;
}
inline bool check(int x,int y){
if(!x&&!y)return true;
if(tree[x].val!=tree[y].val)return false;
return check(tree[x].lch,tree[y].rch)&&check(tree[x].rch,tree[y].lch);
}
inline void dfs(int x){
if(x==0)return;
if(!flag[x]&&tree[x].size>ans)if(check(x,x))ans=tree[x].size;
dfs(tree[x].lch);dfs(tree[x].rch);
return;
}
int main(){
fastread(n);
tree[0]={0,0,0,0};
for(int i=1;i<=n;i++)fastread(tree[i].val);
for(int i=1;i<=n;i++){
fastread(x);fastread(y);
tree[i].lch=(x==-1)?0:x;
tree[i].rch=(y==-1)?0:y;
}
npsize(root);npval(root);
dfs(root);
printf("%d\n",ans);
return 0;
}
然后所有点都TLE了,而且占用空间也很大:

然后到洛谷上找这道题又交了一遍:
后来测试换上以下快读或使用scanf就好了:
inline long long read(){
char c=getchar();
long long val=0,f=1;
while(c<'0'||c>'9')if(c=='-')f=-1,c=getchar();
while('0'<=c&&c<='9')val=(val<<3)+(val<<1)+c-'0',c=getchar();
return val*f;
}
本蒟蒻搞不懂最上面那份快读有什么问题,故发帖求助,请大佬解惑QAQ。