asgshshgadsggsg
2022/3/4 23:45:21
本文主要是介绍asgshshgadsggsg,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<cstdio> #include<deque> #include<algorithm> #define N 1000010 #define ll long long #define fo(x,a,b) for(int x=(a);x<=(b);x++) #define fd(x,a,b) for(int x=(a);x>=(b);x--) using namespace std; inline int read() { int x=0; char c=getchar(); while (c<'0'||c>'9') c=getchar(); while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x; } struct edge { int v,fr; }e[N<<1]; int n,K,m,tail[N],cnt=0,ans=0,lim; int dep[N],mxdep=0,fa[N][20]; inline void add(int u,int v) { e[++cnt]=(edge){v,tail[u]}; tail[u]=cnt; } int siz[N],sta[N],tag[N],dfn[N],st[N],ed[N],tot=0; void dfs(int x) { dfn[++tot]=x,st[x]=tot,siz[x]=1; if (dep[x]>mxdep) mxdep=dep[x]; for (int i=0;fa[fa[x][i]][i];i++) fa[x][i+1]=fa[fa[x][i]][i]; for (int p=tail[x],v;p;p=e[p].fr) { if ((v=e[p].v)==fa[x][0]) continue; fa[v][0]=x,dep[v]=dep[x]+1; dfs(v),siz[x]+=siz[v]; } dfn[++tot]=x,ed[x]=tot; } struct exists { int t[N]; #define lowbit(x) (x&(-x)) void add(int x,int pl) { for (;x<=n;x+=lowbit(x)) t[x]+=pl; } int ask(int x) { int s=0; for (;x;x-=lowbit(x)) s+=t[x]; return s; } void insert(int x,int pl) { add(ed[x],pl),add(st[x]-1,-pl); } int query(int x) { return ask(st[x])-ask(st[x]-1); } #undef lowbit }state,exist; namespace segment_tree { #define ls (x<<1) #define rs (x<<1|1) struct pr { int mx,le,ri,dir,tag; }t[N<<2]; deque<int> dl[N]; const pr spc=(pr){-n,n,n,0,0}; int mxlen[N],len[N]; void search(int x) { int mx1=0,mx2=0; for (int p=tail[x],v;p;p=e[p].fr) { if ((v=e[p].v)==fa[x][0]) continue; if (len[v]>mx1) mx2=mx1,mx1=len[v]; else if (len[v]>mx2) mx2=len[v]; } mxlen[x]=mx1+mx2+1,len[x]=mx1+1; int pos=mxlen[x]/K; bool can=true; if (pos>0) { for (int p=tail[x],v;p;p=e[p].fr) { if ((v=e[p].v)!=fa[x][0]&&mxlen[v]>=pos*K) { can=false; break; } } if (can==true) dl[pos].emplace_back(x); } return; } pr merge(pr x,pr y) { if (x.tag) x=spc; if (y.tag) y=spc; pr now=(pr){0,0,0,0,0}; now.dir=max(x.dir,y.dir); if (x.mx>=y.mx) { now.mx=x.mx; now.le=x.le; now.ri=max({x.ri,y.le,y.ri}); now.dir=max(now.dir,x.mx+y.mx-(min(x.ri,y.le)<<1)+1); } else { now.mx=y.mx; now.ri=y.ri; now.le=max({x.le,x.ri,y.le}); now.dir=max(now.dir,x.mx+y.mx-(min(x.ri,y.le)<<1)+1); } return now; } void make(int x,int l,int r) { if (l==r) { t[x]=(pr){dep[dfn[x]],dep[dfn[x]],dep[dfn[x]],1,0}; return; } int mid=(l+r)>>1; make(ls,l,mid),make(rs,mid+1,r); t[x]=merge(t[ls],t[rs]); return; } void build() { search(1); make(1,1,tot); } void label(int x,int l,int r,int fl,int fr,int pl) { if (fl<=l&&r<=fr) { t[x].tag+=pl; return; } if (t[x].tag) return; int mid=(l+r)>>1; if (fl<=mid) label(ls,l,mid,fl,fr,pl); if (fr>mid) label(rs,mid+1,r,fl,fr,pl); t[x]=merge(t[ls],t[rs]); return; } void modify(int x,int typ) { label(1,1,tot,st[x],ed[x],typ?-1:1); } void calc(int pos) { for (auto x : dl[pos]) exist.insert(x,1); while (!dl[pos].empty()) { int x=dl[pos].front(); dl[pos].pop_front(); if () } } #undef ls #undef rs } int main() { freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); n=read(),K=read(); m=n/K; fo(i,2,n) { int u=read(),v=read(); add(u,v),add(v,u); } dfs(1); mxdep=(mxdep<<1); segment_tree::build(); fo(i,1,m) { int opt=read(); if (opt==1) { int x=read(); x=(x^ans)%n+1; sta[++sta[0]]=x; tag[x]++; if (tag[x]==1) { int res=state.query(x); if (!res) segment_tree::modify(x,0); } state.insert(x,1); ans=0,lim=i*K; if (lim>mxdep) ans=0; else segment_tree::calc(i); printf("%d\n",ans); } else { int x=sta[sta[0]]; sta[0]--; tag[x]--; state.insert(x,-1); if (tag[x]==0) { int res=state.query(x); if (!res) segment_tree::modify(x,1); } ans=0,lim=i*K; if (lim>mxdep) ans=0; else segment_tree::calc(i); printf("%d\n",ans); } } return 0; }
这篇关于asgshshgadsggsg的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南