P4116 Qtree3 树链剖分-路径上第一个标记
程序员文章站
2024-02-14 12:38:28
...
题目链接:https://www.luogu.com.cn/problem/P4116
题目大意:
轻重链剖分后,新的标号仍然满足深度d[u]>d[v],那么id[u]>d[v]。所以现在就可以在线段树上维护区间第一个标记。和单点修改标记。
#include <bits/stdc++.h>
#define Rint register int
using namespace std;
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (r-l+1)
const int maxn=1000005;
int n,m;
//见题意
int tot,head[maxn],nex[maxn],to[maxn], wt[maxn];
//链式前向星数组,w[]、wt[]初始点权数组
int a[maxn<<2];
//线段树数组
int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn];
//son[]重儿子编号,id[]新编号,fa[]父亲节点,cnt dfs_clock/dfs序,dep[]深度,siz[]子树大小,top[]当前链顶端节点
int res;
//查询答案
inline void add(int x,int y){//链式前向星加边
to[++tot]=y;
nex[tot]=head[x];
head[x]=tot;
}
//-------------------------------------- 以下为线段树
inline void build(int rt,int l,int r){
if(l==r){
a[rt]=n+1;
return;
}
build(lson);
build(rson);
a[rt]=min(a[rt<<1], a[rt<<1|1]);
}
inline void update(int rt, int l, int r, int L, int R, int k){//实际上是一个单点修改
if(L<=l&&r<=R){
if(a[rt]==l){
a[rt]=n+1;
}
else{
a[rt]=l;
}
}
else{
if(L<=mid)update(lson,L,R,k);
if(R>mid)update(rson,L,R,k);
a[rt]=min(a[rt<<1], a[rt<<1|1]);
}
}
inline void query(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R){ res=min(res, a[rt]);return;}
else{
if(L<=mid)query(lson,L,R);
if(R>mid)query(rson,L,R);
}
}
//-------------------------------------- 以上为线段树
inline int Q(int x, int y){
res=n+1;
while(top[x]!=top[y]){//当两个点不在同一条链上
if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点
query(1,1,n,id[top[x]],id[x]);//ans加上x点到x所在链顶端 这一段区间的点权和
x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
}
//直到两个点处于一条链上
if(dep[x]>dep[y])swap(x,y);//把x点深度更深的那个点
query(1,1,n,id[x],id[y]);//这时再加上此时两个点的区间和即可
return res;
}
inline void U(int x, int k){
update(1,1,n, id[x], id[x], k);
}
//-------------------------------------- 以下为模板
inline void dfs1(int x,int f,int deep){
dep[x]=deep;
fa[x]=f;
siz[x]=1;
int maxson=-1;
for(Rint i=head[x];i;i=nex[i]){
int y=to[i];
if(y==f)continue;
dfs1(y,x,deep+1);
siz[x]+=siz[y];
if(siz[y]>maxson)son[x]=y,maxson=siz[y];
}
}
inline void dfs2(int x,int topf){
id[x]=++cnt;
wt[cnt]=x;
top[x]=topf;
if(!son[x])return;
dfs2(son[x],topf);
for(Rint i=head[x];i;i=nex[i]){
int y=to[i];
if(y==fa[x]||y==son[x])continue;
dfs2(y,y);
}
}
int main(){
scanf("%d%d", &n, &m);
for(Rint i=1;i<n;i++){
int a,b;
scanf("%d%d", &a, &b);
add(a,b);add(b,a);
}
dfs1(1,0,1);
dfs2(1,1);
build(1,1,n);
while(m--){
int a, b;
scanf("%d%d", &a, &b);
if(a==0){
U(b, 1);//把b点的颜色取反
}
else{
int k=Q(1, b);
if(k==n+1){
printf("-1\n");
}
else{
printf("%d\n", wt[k]);
}
}
}
}
上一篇: OpenFeign的超时设置