首页 > 代码库 > bzoj3083 遥远的国度 题解
bzoj3083 遥远的国度 题解
题目大意：
给定一棵有根树，每个点有一个权值，提供三种操作：
1.将x节点变为根节点
2.将x到y路径上的点的权值全部改为v
3.询问x的子树中点权的最小值
思路：
用DFS序剖分，记录每个节点入栈出栈的时间，其之间的区间即为子树。操作2用线段树直接搞，而换根先不管，可用原来的DFS序。询问时分类讨论：记最开始的根为root，换根之后，对于当前的根rtnow和询问子树U而言，
①rtnow==U，询问整棵树
②fa[rtnow]==U，询问除了rtnow所在子树以外的整棵树
③rtnow在U的子树里，且距离大于1，询问除了rtnow的除了其祖先是U的儿子的祖先的子树以外的整棵树
④rtnow不在U的子树里，询问U的子树
代码：
1 #include<cstdio> 2 #include<iostream> 3 #define M 2000000 4 #define INF 2147483647 5 using namespace std; 6 7 int cnt,dfn,n,m,a[M],to[M],hson[M],next[M],head[M],id[M],size[M],last[M],pos[M],pa[M],deep[M],top[M],cov[M<<2],minv[M<<2]; 8 9 void ins(int x,int y) 10 { 11 to[++cnt]=y,next[cnt]=head[x],head[x]=cnt; 12 } 13 14 void dfs1(int x) 15 { 16 size[x]=1; 17 for (int i=head[x];i;i=next[i]) 18 if (to[i]!=pa[x]) 19 { 20 pa[to[i]]=x,deep[to[i]]=deep[x]+1; 21 dfs1(to[i]),size[x]+=size[to[i]]; 22 if (size[to[i]]>size[hson[x]]) hson[x]=to[i]; 23 } 24 } 25 26 void dfs2(int x,int tp) 27 { 28 id[x]=++dfn,pos[dfn]=x,top[x]=tp; 29 if (hson[x]) dfs2(hson[x],tp); 30 for (int i=head[x];i;i=next[i]) 31 if (to[i]!=pa[x]&&to[i]!=hson[x]) dfs2(to[i],to[i]); 32 last[x]=dfn; 33 } 34 35 void push_down(int k) 36 { 37 if (cov[k]) 38 { 39 cov[k<<1]=cov[k<<1|1]=minv[k<<1]=minv[k<<1|1]=cov[k]; 40 cov[k]=0; 41 } 42 } 43 44 void change(int cur,int L,int R,int l,int r,int val) 45 { 46 if (L==l && R==r) { cov[cur]=minv[cur]=val; return; } 47 int mid=L+R>>1; push_down(cur); 48 if (r<=mid) change(cur<<1,L,mid,l,r,val); 49 else if (l>mid) change(cur<<1|1,mid+1,R,l,r,val); 50 else change(cur<<1,L,mid,l,mid,val),change(cur<<1|1,mid+1,R,mid+1,r,val); 51 minv[cur]=min(minv[cur<<1],minv[cur<<1|1]); 52 } 53 54 int ask(int cur,int L,int R,int l,int r) 55 { 56 if (L==l && R==r) return minv[cur]; 57 int mid=L+R>>1; push_down(cur); 58 if (r<=mid) return ask(cur<<1,L,mid,l,r); 59 if (l>mid) return ask(cur<<1|1,mid+1,R,l,r); 60 return min(ask(cur<<1,L,mid,l,mid),ask(cur<<1|1,mid+1,R,mid+1,r)); 61 } 62 63 void add(int x,int y,int val) 64 { 65 for (;top[x]!=top[y];x=pa[top[x]]) 66 { 67 if (deep[top[x]]<deep[top[y]]) swap(x,y); 68 change(1,1,n,id[top[x]],id[x],val); 69 } 70 if (deep[x]>deep[y]) swap(x,y); 71 change(1,1,n,id[x],id[y],val); 72 } 73 74 int main() 75 { 76 scanf("%d%d",&n,&m); 77 int i,x,y,z,op,rt,root=0; 78 for (i=1;i<n;i++) scanf("%d%d",&x,&y),ins(x,y),ins(y,x); 79 for (i=1;i<=n;i++) scanf("%d",&a[i]); 80 scanf("%d",&rt);dfs1(rt),dfs2(rt,rt); 81 for (i=1;i<=n;i++) change(1,1,n,id[i],id[i],a[i]); 82 while (m--) 83 { 84 scanf("%d",&op); 85 if (op==1) scanf("%d",&root); 86 if (op==2) scanf("%d%d%d",&x,&y,&z),add(x,y,z); 87 if (op==3) 88 { 89 scanf("%d",&x); 90 if (x==root) printf("%d\n",ask(1,1,n,1,n)); 91 else if (pa[root]==x) printf("%d\n",min(ask(1,1,n,1,id[root]-1),last[root]==n?INF:ask(1,1,n,last[root]+1,n))); 92 else if (id[root]>=id[x] && id[root]<=last[x]) 93 { 94 y=root; 95 while (pa[top[y]]!=x && top[x]!=top[y]) y=pa[top[y]]; 96 if (pa[top[y]]!=x) y=pos[id[x]+1]; 97 else y=top[y]; 98 printf("%d\n",min(ask(1,1,n,1,id[y]-1),last[y]==n?INF:ask(1,1,n,last[y]+1,n))); 99 }100 else printf("%d\n",ask(1,1,n,id[x],last[x]));101 }102 }103 return 0;104 }
bzoj3083 遥远的国度 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。