求问大小于号
查看原帖
求问大小于号
1374349
wangkaiwei楼主2025/7/31 19:07

为什么第 5050 行一定要是小于号?

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,fa[100005],dep[100005],siz[100005],son[100005];
int top[100005],id[100005],cnt=0;
vector<int> g[100005];
inline void dfs1(int u,int f){
	dep[u]=dep[f]+1;
	siz[u]=1;
	fa[u]=f;
	int maxx=-1;
	for(register int v:g[u]){
		if(v==f) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>maxx) maxx=siz[v],son[u]=v;
	}
	return;
}
inline void dfs2(int u,int topf){
	top[u]=topf;
	id[u]=++cnt;
	if(!son[u]) return;
	dfs2(son[u],topf);
	for(register int v:g[u]){
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
	return;
}
struct Segment_Tree{
	int t[400005],tag[400005];
	inline void pushdown(int p){
		t[p<<1]=dep[tag[p]]>dep[t[p<<1]]?tag[p]:t[p<<1];
		t[p<<1|1]=dep[tag[p]]>dep[t[p<<1|1]]?tag[p]:t[p<<1|1];
		tag[p<<1]=dep[tag[p]]>dep[tag[p<<1]]?tag[p]:t[p<<1];
		tag[p<<1|1]=dep[tag[p]]>dep[tag[p<<1|1]]?tag[p]:t[p<<1|1];
		tag[p]=0;
	}
	inline void update(int L,int R,int l,int r,int p,int k){
		if(L<=l&&r<=R){
			t[p]=(dep[t[p]]>dep[k])?t[p]:k;
			tag[p]=(dep[tag[p]]>dep[k])?tag[p]:k;
			return;
		}
		int mid=(l+r)>>1;
		pushdown(p);
		if(L<=mid&&dep[k]>dep[t[p<<1]]) update(L,R,l,mid,p<<1,k);
		if(R>mid&&dep[k]>dep[t[p<<1|1]]) update(L,R,mid+1,r,p<<1|1,k);
		t[p]=(dep[t[p<<1]]<dep[t[p<<1|1]])?t[p<<1]:t[p<<1|1];
		return;
	}
	inline int query(int L,int R,int l,int r,int p){
		if(L<=l&&r<=R) return t[p];
		int mid=(l+r)>>1;
		pushdown(p);
		if(L<=mid) return query(L,R,l,mid,p<<1);
		if(R>mid) return query(L,R,mid+1,r,p<<1|1);
	}
}tree;
inline void print(){
	for(int i=1;i<=n;i++) cout<<tree.query(i,i,1,n,1)<<' ';
	cout<<endl;
}
signed main(){
	scanf("%lld%lld",&n,&q);
	for(register int i=1;i<n;i++){
		int u,v;
		scanf("%lld%lld",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,1);
	tree.update(id[1],id[1]+siz[1]-1,1,n,1,1);
	while(q--){
		char op;int x;
		cin>>op>>x;
		if(op=='C') tree.update(id[x],id[x]+siz[x]-1,1,n,1,x);
		if(op=='Q') printf("%lld\n",tree.query(id[x],id[x],1,n,1));
	}
	return 0;
}
2025/7/31 19:07
加载中...