问题 C: 最近公共祖先subset
时间限制: 1 Sec 内存限制: 512 MB
题面
题面谢绝公开。
题解
什么是最近公共祖先？在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点。
而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点。
于是我们考虑bfs预处理+倍增……
以上都是扯淡。下面是真·题解
考虑用线段树维护每一个点的答案。由于一个节点的权值只会对以它为根节点的子树中的节点答案有贡献，我们知道，一个子树的dfs序列一定是连续的。所以可以线段树维护，区间修改。
对于每一次给点$x$染色，分部分考虑该点对整棵树的贡献：
对于以该节点为根的子树：任意一个白点与该节点的公共祖先一定是这个点。所以可以直接用这个节点的权值去更新子树中节点的答案。
特殊地，考虑该节点的父节点$y$。这其中属于$y$的子树而不属于$x$的子树的节点一定可以用其父节点的权值去更新。$y$与其父节点类似更新。
另外，如果我更新到一个节点，当此节点已经用来更新过下面的信息时，可以停止更新。因为上层的节点一定已经被某个黑色节点下放过了。
代码：
#include<bits/stdc++.h>
#define int long long
#define rint register int
using namespace std;
inline void read(int &a)
{
a=0;int b=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')b=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){a=(a<<3)+(a<<1)+ch-'0';ch=getchar();}
a=a*b;return ;
}
int n,m,w[100005],f[100005];
int v[200005],nxt[200005],first[100005],tot;
int l[100005],r[100005],cnt;
char str[35];
bool vis[100005];
struct node{int k,lz;}t[100005<<3];
inline void add(int uu,int vv)
{
v[++tot]=vv,nxt[tot]=first[uu];
first[uu]=tot;return ;
}
inline void dfs(int x,int fa)
{
l[x]=++cnt;f[x]=fa;
for(rint i=first[x];i;i=nxt[i])
if(v[i]!=fa)dfs(v[i],x);
r[x]=cnt;return ;
}
inline void pushdown(int k)
{
t[k<<1].k=max(t[k].lz,t[k<<1].k);
t[k<<1|1].k=max(t[k].lz,t[k<<1|1].k);
t[k<<1].lz=max(t[k].lz,t[k<<1].lz);
t[k<<1|1].lz=max(t[k].lz,t[k<<1|1].lz);
t[k].lz=0;return ;
}
inline void change(int k,int l,int r,int L,int R,int dat)
{
if(L>R)return ;
pushdown(k);
if(L<=l&&r<=R)
{
t[k].k=max(t[k].k,dat);
t[k].lz=max(t[k].lz,dat);
return ;
}
int mid=(l+r)>>1;
if(L<=mid)change(k<<1,l,mid,L,R,dat);
if(R>mid)change(k<<1|1,mid+1,r,L,R,dat);
t[k].k=max(t[k<<1].k,t[k<<1|1].k);
return ;
}
inline int query(int k,int l,int r,int p)
{
pushdown(k);
if(l==r)return t[k].k;
int mid=(l+r)>>1;
if(p<=mid)return query(k<<1,l,mid,p);
else return query(k<<1|1,mid+1,r,p);
}
signed main()
{
//freopen("lca2.in","r",stdin);
//freopen("t3.out","w",stdout);
read(n),read(m);
for(rint i=1;i<=n;++i)read(w[i]);
for(rint i=1,ST,EN;i<n;++i)
{
read(ST),read(EN);
add(ST,EN),add(EN,ST);
}dfs(1,0);
/* for(rint i=1;i<=n;++i)
cout<<l[i]<<' '<<r[i]<<endl;*/
for(rint i=1,vi;i<=m;++i)
{
scanf("%s %lld",str,&vi);
if(str[0]=='M')
{
change(1,1,n,l[vi],r[vi],w[vi]);
vis[vi]=1;
int lc=l[vi],rc=r[vi],lin=0;vi=f[vi];
while(vi&&(!vis[vi]))
{
change(1,1,n,l[vi],lc-1,w[vi]);
change(1,1,n,rc+1,r[vi],w[vi]);
lc=l[vi];rc=r[vi];vi=f[vi];
}
}
else
{
int lin=query(1,1,n,l[vi]);
printf("%lld
",(lin==0)?-1:lin);
}
}
return 0;
}
/*
7 7
4 3 5 7 6 5 2
1 4
2 1
7 5
6 2
2 5
3 4
Qu 1
Mo 2
Mo 4
Qu 3
Mo 2
Mo 5
Qu 6
*/