asgshshgadsggsg

本文主要是介绍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的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！