挺水的一道树剖,弄一下dfs序轻松解决。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<vector>
#include<algorithm>
#define gc getchar()
#define ll long long
#define eps 1e-8
#define ld long double
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=12e5+5;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
int siz[N],son[N],dep[N],fa[N],dfn[N],top[N],yss[N],cnt;
inline int mmax(int x,int y){return dep[x]<dep[y]?y:x;}
struct SGT{int id;bool ex;}t[N<<3];
inline void update(int p){t[p].id=mmax(t[p<<1].id,t[p<<1|1].id);t[p].ex=t[p<<1].ex|t[p<<1|1].ex;}
void build(int p,int l,int r)
{
if(l==r)
{
if(l==1)t[p].id=1,t[p].ex=1;
return ;
}
int mid=l+r>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
update(p);
}
void change(int p,int l,int r,int pos,int v)
{
if(l==r){t[p].id=v;t[p].ex=1;return ;}
int mid=l+r>>1;
if(pos<=mid)change(p<<1,l,mid,pos,v);
else change(p<<1|1,mid+1,r,pos,v);
update(p);
}
int query(int p,int l,int r,int L,int R)
{
if(!t[p].ex)return 0;
if(L<=l&&R>=r)return t[p].id;
int mid=l+r>>1,ls=0,rs=0;
if(R>mid&&t[p<<1|1].ex)rs=query(p<<1|1,mid+1,r,L,R);
if(L<=mid&&t[p<<1].ex)ls=query(p<<1,l,mid,L,R);
return mmax(ls,rs);
}
struct edge{int y,next;}a[N<<1];int last[N],len;
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
void dfs1(int x)
{
siz[x]=1;son[x]=0;
for(int k=last[x],y;k;k=a[k].next)
{
if((y=a[k].y)==fa[x])continue;
fa[y]=x;dep[y]=dep[x]+1;
dfs1(y);
siz[x]+=siz[y];if(siz[son[x]]<siz[y])son[x]=y;
}
}
void dfs2(int x,int tp)
{
dfn[x]=++cnt;yss[cnt]=x;top[x]=tp;
if(son[x])dfs2(son[x],tp);
for(int k=last[x],y;k;k=a[k].next)
if((y=a[k].y)!=fa[x]&&y!=son[x])dfs2(y,y);
}
int n,m;
int solve(int x)
{
while(top[x]!=1)
{
int val=query(1,1,n,dfn[top[x]],dfn[x]);
if(val)return val;
x=fa[top[x]];
}
return query(1,1,n,dfn[top[x]],dfn[x]);
}
int main()
{
//freopen("tree11.in","r",stdin);
//freopen("tree11.ans","w",stdout);
qr(n),qr(m);
for(int i=1,x,y;i<n;i++)qr(x),qr(y),ins(x,y),ins(y,x);
dep[1]=1;dfs1(1);
dfs2(1,1);
build(1,1,n);
for(int i=1;i<=m;i++)
{
char op[2];int x;scanf("%s",op);qr(x);
if(op[0]=='Q')qw(solve(x)),puts("");
else change(1,1,n,dfn[x],x);
}
return 0;
}
最后一次更新于2020-04-15
0 条评论