P3250 [HNOI2016] 网络 （树剖+堆）

本文主要是介绍P3250 [HNOI2016] 网络 （树剖+堆），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

本题有插入路径和删除路径，在每个节点维护插入堆和删除堆，查询时两者top一样则一直弹出。如果每个节点维护的是经过他的路径，显然有些不好处理，正难则反，每个点维护不经过他的路径，那么x节点出了故障时，我们就查询x，查询到的就是x出故障后不受影响的路径。

（洛谷上有一个点一直过不了，似乎是之后加强过的数据）。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int N=200010;
  4 int tot,sum,head[N],nxt[N<<1],to[N<<1],id[N],top[N],sze[N],son[N],dep[N],fa[N];
  5 int n,m;
  6 
  7 inline void add(int x,int y){
  8     nxt[++tot]=head[x];
  9     head[x]=tot;
 10     to[tot]=y;
 11 }
 12 
 13 inline int read()
 14 {
 15   int x=0,flag=1;
 16   char ch=getchar();
 17   while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}
 18   while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
 19   return x*flag;
 20 }
 21 
 22 struct node{//每个节点存两个堆 
 23     priority_queue<int>a,d;
 24     void push(int x){a.push(x);}
 25     void del(int x){d.push(x);}
 26     int top(){
 27         while(!d.empty()&&a.top()==d.top()) a.pop(),d.pop();
 28         if(a.empty()) return -1;
 29         return a.top();
 30     }
 31 }t[N*5];
 32 
 33 struct ac{
 34     int x,y,z;
 35 }q[N];
 36 
 37 struct AC{
 38     int l,r;
 39 }Data[N];
 40 
 41 inline void dfs1(int x,int f){
 42     dep[x]=dep[f]+1,fa[x]=f,sze[x]=1;
 43     for(register int i=head[x];i;i=nxt[i]){
 44         int y=to[i];
 45         if(y==f) continue;
 46         dfs1(y,x);
 47         sze[x]+=sze[y];
 48         if(sze[y]>=sze[son[x]]) son[x]=y;//曾老给的数据要卡这一步 
 49     }
 50 }
 51 
 52 inline void dfs2(int x,int t){
 53     top[x]=t;
 54     id[x]=++sum;
 55     if(!son[x]) return ;
 56     dfs2(son[x],t);
 57     for(register int i=head[x];i;i=nxt[i]){
 58         int y=to[i];
 59         if(y!=fa[x]&&y!=son[x])
 60             dfs2(y,y);
 61     }
 62 }
 63 
 64 bool cmp(AC a,AC b){
 65     return a.l<b.l;
 66 }
 67 
 68 inline void modify(int k,int l,int r,int L,int R,int type,int val){
 69     if(L>R) return ;
 70     if(L<=l&&R>=r){
 71         if(!type) t[k].push(val);
 72         else t[k].del(val);
 73         return ;
 74     }
 75     int mid=(l+r)>>1;
 76     if(L<=mid) modify(k<<1,l,mid,L,R,type,val);
 77     if(R>mid) modify(k<<1|1,mid+1,r,L,R,type,val);
 78 }
 79 
 80 inline void update(int x,int y,int type,int val){
 81     int cnt=0;
 82     while(top[x]!=top[y]){
 83         if(dep[top[x]]<dep[top[y]]) swap(x,y);
 84         Data[++cnt]=(AC){id[top[x]],id[x]};
 85         x=fa[top[x]];
 86     }
 87     if(dep[x]<dep[y]) swap(x,y);
 88     Data[++cnt]=(AC){id[y],id[x]};
 89     sort(Data+1,Data+cnt+1,cmp);
 90     int last=1;
 91     for(register int i=1;i<=cnt;i++) modify(1,1,n,last,Data[i].l-1,type,val),last=Data[i].r+1;
 92     modify(1,1,n,last,n,type,val);
 93 }
 94 
 95 inline int query(int k,int l,int r,int x){
 96     if(l==r&&l==x)
 97         return t[k].top();
 98     int mid=(l+r)>>1;
 99     if(x<=mid) return max(t[k].top(),query(k<<1,l,mid,x));
100     else return max(t[k].top(),query(k<<1|1,mid+1,r,x));
101 }
102 
103 int main(){
104     int x,y,z,type;
105     n=read(),m=read();
106     for(register int i=1;i<n;i++){
107         x=read(),y=read();
108         add(x,y);add(y,x);
109     }
110     dfs1(1,0);dfs2(1,1);//树链剖分 
111     for(register int i=1;i<=m;i++){
112         type=read();
113         if(type==0){
114             x=read(),y=read(),z=read();
115             update(x,y,0,z);
116             q[i]=(ac){x,y,z};//存每条交互链 
117         }
118         if(type==1){
119             x=read();
120             update(q[x].x,q[x].y,1,q[x].z);
121         }
122         if(type==2){
123             x=read();
124             printf("%d\n",query(1,1,n,id[x]));
125         }
126     }
127     return 0;
128 }

这篇关于P3250 [HNOI2016] 网络 （树剖+堆）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！