https://www.luogu.org/problem/P4092
给定一颗有根树,根为 11,有以下两种操作:
-
标记操作:对某个结点打上标记。(在最开始,只有结点 11 有标记,其他结点均无标记,而且对于某个结点,可以打多次标记。)
-
询问操作:询问某个结点最近的一个打了标记的祖先。(这个结点本身也算自己的祖先)
你能帮帮她吗?
输入格式
第一行两个正整数 N 和 Q 分别表示节点个数和操作次数。
接下来 N-1 行,每行两个正整数 u,v(1⩽u,v⩽n) 表示 u 到 v 有一条有向边。
接下来 Q 行,形如 oper num
,oper
为 C
时表示这是一个标记操作, oper
为 Q
时表示这是一个询问操作。
dfs序上搞线段树就行
线段树维护两个值
一个值表示每个点的深度最大的祖先(也就是最近祖先)用于维护更新,一个表示点编号,用于输出答案
#include<iostream> #include<cstdio> #include<algorithm> #define ri register int #define u int #define NN 100005 namespace fast { inline u in() { u x(0),f(1); char s=getchar(); while(s<'0'||s>'9') { if(s=='-') { f=-1; } s=getchar(); } while(s>='0'&&s<='9') { x=(x<<1)+(x<<3)+s-'0'; s=getchar(); } return x*f; } } using fast::in; using std::max; namespace xds { u a[NN<<2],ans[NN<<2],aaa[NN<<2],add[NN<<2],sum[NN<<2]; void build(const u &rt,const u &l,const u &r) { if(l==r) { sum[rt]=ans[rt]=a[l]=1; return; } u mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); sum[rt]=max(sum[rt<<1],sum[rt<<1|1]); } void pushdown(const u &rt,const u &l,const u &r) { if(!add[rt]) return; u xrt=rt<<1; u mid=(r+l)>>1; if(sum[xrt]<add[rt]) { sum[xrt]=add[rt]; ans[xrt]=aaa[rt]; } if(sum[xrt|1]<add[rt]) { sum[xrt|1]=add[rt]; ans[xrt|1]=aaa[rt]; } if(add[xrt]<add[rt]) { add[xrt]=add[rt]; aaa[xrt]=aaa[rt]; } if(add[xrt|1]<add[rt]) { add[xrt|1]=add[rt]; aaa[xrt|1]=aaa[rt]; } add[rt]=aaa[rt]=0; } void update(const u &rt,const u &l,const u &r,const u &x,const u &y,const u &v,const u &p) { if(x<=l&&y>=r) { if(sum[rt]<v) { sum[rt]=v; ans[rt]=p; } if(add[rt]<v) { add[rt]=v; aaa[rt]=p; } return; } pushdown(rt,l,r); u mid=(l+r)>>1; if(x<=mid) { update(rt<<1,l,mid,x,y,v,p); } if(mid<y) { update(rt<<1|1,mid+1,r,x,y,v,p); } sum[rt]=max(sum[rt<<1],sum[rt<<1|1]); } u query(const u &rt,const u &l,const u &r,const u &x) { if(l==r) { return ans[rt]; } pushdown(rt,l,r); u mid=(r+l)>>1,re(0); if(x<=mid) { re=query(rt<<1,l,mid,x); } else { re=query(rt<<1|1,mid+1,r,x); } return re; } } namespace all { u N,Q,n; u h[NN],d[NN],cnt; struct node { u to,next; } a[NN<<1]; struct point { u l,r; } p[NN]; inline void add(const u &x,const u &y) { a[++cnt].to=y,a[cnt].next=h[x],h[x]=+cnt; } u dfs(const u &x,const u &prt,const u &deep) { p[x].l=++n,d[x]=deep; for(ri i(h[x]); i; i=a[i].next) { u _y(a[i].to); if(_y^prt) { p[x].r=std::max(p[x].r,dfs(_y,x,deep+1)); } } if(!p[x].r) p[x].r=p[x].l; return p[x].r; } inline void solve() { N=in(),Q=in(); xds::build(1,1,N); for(ri i(1); i<N; ++i) { u _a(in()),_b(in()); add(_a,_b),add(_b,_a); } dfs(1,0,1); for(ri i(1); i<=Q; ++i) { char _s(getchar()); while(_s!='Q'&_s!='C')_s=getchar(); u _x(in()); if(_s=='Q') { printf("%d\n",xds::query(1,1,N,p[_x].l)); } else { xds::update(1,1,N,p[_x].l,p[_x].r,d[_x],_x); } } } } int main() { //freopen("4551.in","r",stdin); //freopen("4551.out","w",stdout); all::solve(); }