CF1527D MEX Tree(mex&树&容斥)

CF1527D MEX Tree(mex&树&容斥)

CF1527D MEX Tree(mex&树&容斥)

考虑从小到大递推。

#includeusing namespace std;#define ri register inttypedef long long ll;const int maxn=2e5+10;struct node{ int to,nxt;}e[maxn<<1];int hd[maxn],len;inline void addedge(int fr,int to){ e[++len]={to,hd[fr]}; hd[fr]=len;}int dep[maxn],fa[maxn],n,son[maxn],t,top[maxn];ll siz[maxn];void dfs1(int p,int f){ dep[p]=dep[f]+1; fa[p]=f; siz[p]=1; for(ri i=hd[p];i;i=e[i].nxt) if(e[i].to!=f){ dfs1(e[i].to,p); siz[p]+=siz[e[i].to]; if(siz[e[i].to]>siz[son[p]])son[p]=e[i].to; }}void dfs2(int p,int k){ top[p]=k; if(son[p]){ dfs2(son[p],k); for(ri i=hd[p];i;i=e[i].nxt) if(!top[e[i].to]) dfs2(e[i].to,e[i].to); }}inline int lca(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]1;j=fa[j],sl=siz[j]); } l=i; } else if(b==r&&a==1){ if(r==1){ sr=siz[i]; for(ri j=i;fa[j]>1;j=fa[j],sr=siz[j]); } r=i; } else if(a!=i&&b!=i)break; if(l==1)ans[i]=siz[r]*(n-sr); else if(r==1)ans[i]=siz[l]*(n-sl); else ans[i]=siz[l]*siz[r]; } for(ri i=2;i<=n+1;++i)printf(" %lld",ans[i-1]-ans[i]); printf("\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。