题目:QTREE6 - Query on a tree VI。
去掉快读只有四十行。
#include<bits/stdc++.h>
#define EL puts("Elaina")
#define reg register int
using namespace std;
namespace IO{
const int siz=1<<18;char buf[siz],*p1,*p2;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,siz,stdin),p1==p2)?EOF:*p1++;}
inline int read(){
int x=0;char ch=getc();
while(!isdigit(ch))ch=getc();
while(isdigit(ch))x=x*10+(ch^48),ch=getc();
return x;
}
}using IO::read;
const int maxn=1e5+3;
struct{int to,next;}e[maxn<<1];
int len,head[maxn],siz[maxn],son[maxn],fa[maxn],top[maxn],dfn[maxn],raw[maxn],ti;
inline void insert(int from,int to){e[++len].to=to,e[len].next=head[from],head[from]=len;}
inline void dfs1(int u){
for(reg i=(siz[u]=1,head[u]),v;i;i=e[i].next)
if((v=e[i].to)^fa[u]&&(fa[v]=u,dfs1(v),siz[u]+=siz[v],siz[v]>siz[son[u]]))son[u]=v;
}
set<int> S[2][maxn];
inline void dfs2(int u,int t){
raw[*S[0][top[u]=t].insert(dfn[u]=++ti).first]=u;
if(son[u]&&(dfs2(son[u],t),1))for(reg i=head[u],v;i;i=e[i].next)if((v=e[i].to)^fa[u]&&v^son[u])dfs2(v,v);
}
int n,rof[2][maxn];bool col[maxn];
struct BIT{
int t[maxn];
inline void update(int i,int x){if(i)while(i<=n)t[i]+=x,i+=i&-i;}
inline int query(int i){int ans=0;while(i)ans+=t[i],i^=i&-i;return ans;}
inline int size(int u){return query(dfn[u]+siz[u]-1)-query(dfn[u]-1);}
}t[2];
inline int ancestor(int u){
int x=u,y,z;while(x&&rof[col[u]^1][top[x]]>dfn[x])x=fa[y=top[x]];
return x?(z=raw[*--S[col[u]^1][top[x]].upper_bound(dfn[x])])==x?y:son[z]:1;
}
inline void MyDearMoments(){
for(reg i=(n=read(),1),x,y;i<n;++i)insert(x=read(),y=read()),insert(y,x);
for(reg i=(dfs1(1),dfs2(1,1),1);i<=n;++i)t[0].t[i]=i&-i,t[1].update(dfn[i],1),t[1].update(dfn[fa[i]],-1);
for(reg i=1;i<=n;++i)if(top[i]==i)rof[1][i]=INT_MAX,rof[0][i]=dfn[i];
for(reg Q=read(),opt,u,y,z;Q--;)if(opt=read(),u=read(),opt){
t[col[u]].update(dfn[fa[u]],z=-t[col[u]].size(u)),t[col[u]].update(dfn[fa[(y=ancestor(u))^1&&(y=fa[y]),y]],-z);
S[col[u]][y=top[u]].erase(dfn[u]),rof[col[u]][y]=S[col[u]][y].size()?*S[col[u]][y].begin():INT_MAX;
S[col[u]^=1][y].insert(dfn[u]),rof[col[u]][y]=*S[col[u]][y].begin();
t[col[u]].update(dfn[fa[u]],z=t[col[u]].size(u)),t[col[u]].update(dfn[fa[(y=ancestor(u))^1&&(y=fa[y]),y]],-z);
}else printf("%d\n",t[col[u]].size(ancestor(u)));
}
int main(){return MyDearMoments(),0;}
可以使代码行数显著减少,并且这种码风码量也会少一些,思维更加密集连贯。
缺点:没有容错率,很难调。信息熵较大而可读性较低。
标签:int,top,son,maxn,码风,猎奇,reg From: https://www.cnblogs.com/muel-imj/p/16904877.html