P4092 [HEOI2016/TJOI2016]树 [ 树剖]

本文主要是介绍P4092 [HEOI2016/TJOI2016]树 [ 树剖]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

单点修改 , 链查询查到了就break 

线段树查询时先找到区间 , 区间内尽量往右边找 , 这样深度更大

#include<bits/stdc++.h>
#define N 100050
#define M N*2
using namespace std;
int n,m,tag[N];
int first[N],next[M],to[M],tot;
int id[N],siz[N],dep[N],fa[N],son[N],top[N],pre[N],sign;
int val[N<<2];void add(int x,int y){next[++tot]=first[x],first[x]=tot,to[tot]=y;
}
void dfs1(int u,int f){siz[u]=1;for(int i=first[u];i;i=next[i]){int t=to[i]; if(t==f) continue;fa[t] = u , dep[t] = dep[u] + 1;dfs1(t,u); siz[u] += siz[t]; if(siz[son[u]]<siz[t]) son[u] = t;} 
}
void dfs2(int u,int Top){id[u] = ++sign; pre[sign] = u;top[u] = Top;if(son[u]) dfs2(son[u],Top);for(int i=first[u];i;i=next[i]){int t=to[i]; if(t==son[u] || t==fa[u]) continue;dfs2(t,t);}
}void Pushup(int x){val[x] = val[x<<1] + val[x<<1|1];
}
void Insert(int x,int l,int r,int pos,int v){if(l==r){ val[x] = v; return;}int mid = (l+r) >> 1;if(pos<=mid) Insert(x<<1,l,mid,pos,v);else Insert(x<<1|1,mid+1,r,pos,v);Pushup(x);
}
void Q(int x,int l,int r,int &ans){if(l==r && val[x]){ ans = max(ans,l); return;}int mid = (l+r) >> 1;if(val[x<<1|1]) Q(x<<1|1,mid+1,r,ans);else Q(x<<1,l,mid,ans);
}
void Tree_Q(int x,int l,int r,int L,int R,int &ans){if(L<=l && r<=R){if(val[x]) Q(x,l,r,ans); return;}int mid = (l+r) >> 1;if(L<=mid) Tree_Q(x<<1,l,mid,L,R,ans);if(R>mid) Tree_Q(x<<1|1,mid+1,r,L,R,ans);
}
int Quary(int x){while(top[x]!=1){int tmp=0;  Tree_Q(1,1,n,id[top[x]],id[x],tmp);if(tmp) return pre[tmp];x = fa[top[x]];} int tmp = 0; Tree_Q(1,1,n,id[1],id[x],tmp);return pre[tmp];
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<n;i++){int x,y; scanf("%d%d",&x,&y);add(x,y),add(y,x);} dfs1(1,0); dfs2(1,1); tag[1] = 1; Insert(1,1,n,1,id[1]);while(m--){char s[3]; scanf("%s",s); int x; scanf("%d",&x);if(s[0]=='Q') printf("%d\n",Quary(x));if(s[0]=='C') if(!tag[x]) Insert(1,1,n,id[x],1), tag[x] = 1; } return 0;
}

 

这篇关于P4092 [HEOI2016/TJOI2016]树 [ 树剖]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---