【BZOJ 3306】树【LCA、DFS序、线段树】

Description

给定一棵大小为 n 的有根点权树,支持以下操作: 　　1、 换根 　　2、 修改点权 　　3、 查询子树最小值

Input

　　第一行两个整数 n, Q ,分别表示树的大小和操作数。 　　接下来n行,每行两个整数f,v,第i+1行的两个数表示点i的父亲和点i的权。保证f < i。如 果f = 0,那么i为根。输入数据保证只有i = 1时,f = 0。 　　接下来 m 行,为以下格式中的一种: 　　• V x y表示把点x的权改为y 　　• E x 表示把有根树的根改为点 x 　　• Q x 表示查询点 x 的子树最小值

Solution

　　网上有人用 LCT ，但感觉没这个必要。我们看看怎么用以 1 为根的树解决此题。 　　 　　对于预处理，先将树的DFS序跑出来，在到达每个点和离开每个点时做标记 fi[] 和 se[] ，在此基础上用一个线段树维护。 　　 　　其次，在读入完毕后可用倍增法预处理以 1 为根的树的LCA。 　　 　　好了，想在讲正题——如何处理这三个操作： 　　 　　1、权值修改：直接在线段树上做位置为 fi[x] 和 se[x] 的单点修改。 　　 　　2、换根：直接标记 root=y 　　 　　3、查询：这才是这道题的重点，已知现在的根 root ，考虑 x 的子树，我们要分成3种情况： 　　　①x==root，直接输出整棵树的最小值。 　　　 　　　② lca(x,root)<>x ，你可以画一个图，在以 1 为根的情况下，这样只需直接查询以x为根的子树的最小值，即在线段树查询区间fi[x] se[x]。 　　　 　　　③ lca(x,root)==x ，这时从以 1 为根的树中看，root在 x 子树内。找到x到 root 路径中最接近 x 的结点y，然后查询的时候踢开以 y 为根的子树范围，即ans=min(query(1,fi[y]−1),query(se[y] 1,tim))

Code

#include<cstdio> #include<cstring> #include<algorithm> #define N 100100 using namespace std; struct Edge{int to,next;}e[N<<1]; int head[N],m,tim; int seq[N<<1],dep[N],fi[N],se[N],a[N]; int fa[19][N]; int n,root; void init() { tim = m = 0; memset(head,0,sizeof(head)); memset(fa,-1,sizeof(fa)); } void add_edge(int from,int to) { e[++m].next = head[from]; head[from] = m; e[m].to = to; } void dfs(int v,int d) { seq[++tim] = v; fi[v] = tim; dep[v] = d; for(int i = head[v];i;i=e[i].next) if(e[i].to != fa[0][i]) dfs(e[i].to,d+1); seq[++tim] = v; se[v] = tim; } void pre() { dfs(1,0); for(int k = 0;k + 1 < 19;k++) for(int v = 1;v <= n;v++) if(fa[k][v] < 0) fa[k+1][v] = -1; else fa[k+1][v] = fa[k][ fa[k][v] ]; } int lca(int u,int v) { if(dep[u] > dep[v]) swap(u,v); for(int k = 0;k < 18;k++) if( (dep[v]-dep[u])>>k & 1) v = fa[k][v]; if(v == u) return u; for(int k = 17;k >= 0;k--) if(fa[k][v] != fa[k][u]) { v = fa[k][v]; u = fa[k][u]; } return fa[0][u]; } int find(int x,int v)//这里是用于情况3中的③操作 { for(int k = 17;k >= 0;k--) if(dep[fa[k][v]] > dep[x]) v = fa[k][v]; return v; } #define lson o << 1 #define rson o << 1 | 1 const int inf = 2000112008; int minn[N<<3]; void pushup(int o) { minn[o] = min(minn[lson],minn[rson]); } void build(int o,int l,int r) { if(l == r) { minn[o] = a[seq[l]]; return; } int mid = (l+r)>>1; build(lson,l,mid); build(rson,mid+1,r); pushup(o); } void update(int o,int l,int r,int pos,int v) { if(l == r) {minn[o] = v; return; } int mid = (l+r)>>1; if(pos <= mid) update(lson,l,mid,pos,v); else update(rson,mid+1,r,pos,v); pushup(o); } int query(int o,int l,int r,int ll,int rr) { if(ll <= l && rr >= r) return minn[o]; int mid = (l+r)>>1,ans = inf; if(ll <= mid) ans = min(ans,query(lson,l,mid,ll,rr)); if(rr > mid) ans = min(ans,query(rson,mid+1,r,ll,rr)); return ans; } int main() { char opt[3]; int q,x,y; init(); scanf("%d%d",&n,&q); for(int i = 1;i <= n;i++) { scanf("%d%d",&fa[0][i],&a[i]); add_edge(fa[0][i],i); } pre(); root = 1; build(1,1,tim); while(q--) { scanf("%s%d",opt,&x); if(opt[0] == 'V') { scanf("%d",&y); update(1,1,tim,fi[x],y); update(1,1,tim,se[x],y); } if(opt[0] == 'E') root = x; if(opt[0] == 'Q') { if(x == root) printf("%d\n",query(1,1,tim,1,tim)); else { y = lca(x,root); if(y != x) printf("%d\n",query(1,1,tim,fi[x],se[x])); else { y = find(x,root); int ans = inf; if(fi[y]-1 >= 1) ans = min(ans,query(1,1,tim,1,fi[y]-1)); if(se[y]+1 <= tim) ans = min(ans,query(1,1,tim,se[y]+1,tim)); printf("%d\n",ans); } } } } return 0; }