【jzoj5221】【GDOI2018模拟7.10】【A】【线段树合并】

题目大意

解题思路

从下往上建权值线段树，用子树的线段树合并出当前的线段树，维护最大连续区间和size即可。

code

#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define LF double #define LL long long #define ULL unsigned int #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) #define fr(i,j) for(int i=begin[j];i;i=next[i]) using namespace std; int max(int x,int y){return (x>y)?x:y;} int min(int x,int y){return (x<y)?x:y;} int const mn=1e5+9,mp=18*1e5+9,inf=1e9+7; int n,gra,pon,ans,begin[mn],to[mn],next[mn],num[mn],pre[mn],mx[mp],lmx[mp], rmx[mp],size[mp],son[mp][2]; void insert(int u,int v){ to[++gra]=v; next[gra]=begin[u]; begin[u]=gra; } void update(int p,int l,int r,int md){ int ls=son[p][0],rs=son[p][1]; mx[p]=max(max(mx[ls],mx[rs]),rmx[ls]+lmx[rs]); lmx[p]=(lmx[ls]==md-l+1)?md-l+1+lmx[rs]:lmx[ls]; rmx[p]=(rmx[rs]==r-md)?r-md+rmx[ls]:rmx[rs]; size[p]=size[ls]+size[rs]; } void oper(int p,int l,int r,int v){ int md=(l+r)/2; if(l==r){ mx[p]=lmx[p]=rmx[p]=size[p]=1; return; } if(v<=md){ if(!son[p][0])son[p][0]=++pon; oper(son[p][0],l,md,v); }else{ if(!son[p][1])son[p][1]=++pon; oper(son[p][1],md+1,r,v); } update(p,l,r,md); } int merge(int p,int q,int l,int r){ if(size[p]<size[q])swap(p,q); if(!size[q])return p; int md=(l+r)/2; son[p][0]=merge(son[p][0],son[q][0],l,md); son[p][1]=merge(son[p][1],son[q][1],md+1,r); update(p,l,r,md); return p; } void dfs(int now){ num[now]=++pon; oper(pon,1,n,now); fr(i,now){ dfs(to[i]); num[now]=merge(num[now],num[to[i]],1,n); } if((mx[num[now]]>5)&&(mx[num[now]]!=n)&&(mx[num[now]]==size[num[now]])){ int bb; bb++; } ans+=mx[num[now]]==size[num[now]]; } int main(){ freopen("d.in","r",stdin); freopen("d.out","w",stdout); scanf("%d",&n); fo(i,1,n-1){ int u,v; scanf("%d%d",&u,&v); insert(u,v); pre[v]++; } int rt; fo(i,1,n)if(!pre[i]){rt=i;break;} dfs(rt); printf("%d",ans); return 0; }