首页 > 代码库 > [BZOJ 3306]树（dfs序+线段树+倍增）
[BZOJ 3306]树（dfs序+线段树+倍增）
Description
给定一棵大小为 n 的有根点权树,支持以下操作:
• 换根
• 修改点权
• 查询子树最小值
Solution
单点修改子树查询的话可以想到用dfs序+线段树来处理，换根的处理画一画图应该可以明白：
如果查询的x是当前的根rt，直接返回整棵树的min
如果rt在x的子树中，用倍增的方法找到离x最近的rt的祖先t，整棵树除t的子树以外的部分就是x当前根下的子树
如果rt不在x的子树中，查询x原来的子树的min值
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#define MAXN 100005#define INF 0x3f3f3f3fusing namespace std;int n,q,head[MAXN],cnt=0,rt=0,w[MAXN],p[MAXN][20],deep[MAXN];int a[MAXN],in[MAXN],out[MAXN],dfn_clock=0;struct Node1{ int l,r,minn;}t[MAXN*4];struct Node2{ int next,to;}Edges[MAXN*2];void addedge(int u,int v){ Edges[++cnt].next=head[u]; head[u]=cnt; Edges[cnt].to=v;}int read(){ int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}void dfs(int u){ a[++dfn_clock]=u;in[u]=dfn_clock; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(v==p[u][0])continue; deep[v]=deep[u]+1;dfs(v); } out[u]=dfn_clock;}void init(){ for(int i=1;i<=16;i++) { for(int j=1;j<=n;j++) p[j][i]=p[p[j][i-1]][i-1]; }}void build(int idx,int l,int r){ t[idx].l=l,t[idx].r=r; if(l==r){t[idx].minn=w[a[l]];return;} int mid=(l+r)>>1; build(idx<<1,l,mid),build(idx<<1|1,mid+1,r); t[idx].minn=min(t[idx<<1].minn,t[idx<<1|1].minn);}void change(int idx,int p,int v){ if(t[idx].l==t[idx].r){t[idx].minn=v;return;} int mid=(t[idx].l+t[idx].r)>>1; if(p<=mid)change(idx<<1,p,v); else change(idx<<1|1,p,v); t[idx].minn=min(t[idx<<1].minn,t[idx<<1|1].minn);}int query(int idx,int l,int r){ if(l>r)return INF; if(l<=t[idx].l&&r>=t[idx].r)return t[idx].minn; int mid=(t[idx].l+t[idx].r)>>1; if(r<=mid)return query(idx<<1,l,r); else if(l>mid)return query(idx<<1|1,l,r); else return min(query(idx<<1,l,r),query(idx<<1|1,l,r));}int main(){ memset(head,-1,sizeof(head)); n=read(),q=read(); for(int i=1;i<=n;i++) { p[i][0]=read(),w[i]=read(); if(!p[i][0])rt=i; addedge(p[i][0],i); } dfs(rt),init(); build(1,1,n); for(int i=1;i<=q;i++) { char opt[2];int x,y; scanf("%s",opt); if(opt[0]==‘V‘) x=read(),y=read(),change(1,in[x],y); else if(opt[0]==‘E‘) {x=read();rt=x;} else { x=read(); if(x==rt)printf("%d\n",query(1,1,n)); else if(in[rt]>=in[x]&&out[rt]<=out[x]) { int f=deep[rt]-deep[x]-1,t=rt; for(int j=0;j<=18;j++) if(f&(1<<j))t=p[t][j]; printf("%d\n",min(query(1,1,in[t]-1),query(1,out[t]+1,n))); } else printf("%d\n",query(1,in[x],out[x])); } } return 0;}
[BZOJ 3306]树（dfs序+线段树+倍增）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。