最近公共祖先
问题描述
给定一棵(n)个节点的有根树，节点编号为(1sim n)，其中根节点为(1)号节点。每个节点都对应着一种颜色（黑/白）和一个固定的权值，初始时所有节点的颜色都为白色。现在你需要实现以下两种操作：
- ( t{Modify v})：将节点(v)的颜色改成黑色；
- ( t{Query v})：找到一个黑色节点(u)，使得节点(u)和(v)的最近公共祖先(z)对应的权值尽可能大，输出节点(z)的权值。如果不存在黑色节点，输出(-1)
输入格式
第一行两个正整数(n,m)，表示节点数和操作数。
第二行(n)个正整数(w_1,w_2,dots,w_n(w_ile 10^9))，表示(n)个节点的权值。
接下来(n-1)行，每行两个正整数(a_i,b_i)，表示节点(a_i)与节点(b_i)之间有一条边相连。
接下来(m)行，每行由一个字符串(str)和一个正整数(v)组成，分别表示操作类型以及操作对应的节点编号。
输出格式
对于每个询问操作，输出一个整数作为这个询问的答案。
说明
对于(10\%)的数据：(nle 100,mle 200)
对于(20\%)的数据：(nle 3000,mle 3000)
对于另外(20\%)的数据：保证数据随机生成
对于另外(20\%)的数据：保证( t{Query})操作在所有( t{Modify})操作完成之后
对于(100\%)的数据：(nle 100000,mle 200000)
sb题放(T3)了就没做出来（其实还是太菜，和放(T3)没得关系
最后一个另(20\%)的数据还星，要做个从上到下的树形( t{dp})，是一个不错的想法。
大概说一下，(dp_i)代表(i)节点通过(i)子树以外的黑点得到的最大(LCA)值。
转移
子树(i)-子树(v)有黑点，(dp_v=max(dp_i,w_i))；
否则，(dp_v=dp_i)
注意最后自己是黑点还要更新一下子树。
下面正解
题目有个重点，节点只会被染黑而不会被染回去。
如果一个节点黑了，它的每个祖先节点可以对 除了这个点所在儿子的子树外 的自己子树的所有点做出贡献，直接对一个子树-子树的点集算上( t{Ta})的贡献就可以了。
一个点被两个来自不同儿子的点算了以后，就没必要管( t{Ta})
因此每个点计算贡献的次数是(O(n))的
对子树跑一下(DFS)序，线段树维护一下区间修改和单点最大值就可以了。
Code:
#include <cstdio>
#include <cstring>
const int N=1e5+10;
int head[N],to[N<<1],Next[N<<1],cnt;
void add(int u,int v)
{
to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
int f[N],dfn[N],low[N],poi[N],dfs_clock,m,n,is[N];
void dfs(int now)
{
dfn[now]=++dfs_clock;
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
if(v==f[now]) continue;
f[v]=now;
dfs(v);
}
low[now]=dfs_clock;
}
#define ls id<<1
#define rs id<<1|1
int max(int x,int y){return x>y?x:y;}
int tag[N<<2];
void change(int id,int L,int R,int l,int r,int d)
{
if(r<l||!l) return;
if(L==l&&R==r)
{
tag[id]=max(tag[id],d);
return;
}
int Mid=L+R>>1;
if(r<=Mid) change(ls,L,Mid,l,r,d);
else if(l>Mid) change(rs,Mid+1,R,l,r,d);
else change(ls,L,Mid,l,Mid,d),change(rs,Mid+1,R,Mid+1,r,d);
}
int query(int id,int l,int r,int p)
{
if(l==r) return tag[id];
int mid=l+r>>1;
if(p<=mid) return max(tag[id],query(ls,l,mid,p));
else return max(tag[id],query(rs,mid+1,r,p));
}
int main()
{
memset(tag,-1,sizeof(tag));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",poi+i);
for(int u,v,i=1;i<n;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
dfs(1);
char s[8];is[0]=1;
for(int las,v,i=1;i<=m;i++)
{
scanf("%s%d",s,&v);
if(s[0]=='Q')
printf("%d
",query(1,1,n,dfn[v]));
else
{
change(1,1,n,dfn[v],low[v],poi[v]);
las=v,is[v]=1,v=f[v];
do
{
change(1,1,n,dfn[v],dfn[las]-1,poi[v]);
change(1,1,n,low[las]+1,low[v],poi[v]);
las=v,is[v]=1,v=f[v];
}while(!is[v]);
change(1,1,n,dfn[v],dfn[las]-1,poi[v]);
change(1,1,n,low[las]+1,low[v],poi[v]);
}
}
return 0;
}
2018.10.30