题解 P3250 【[HNOI2016]网络】

由于这道题的操作只与两个点之间的路径有关，因此以哪个节点为根不影响结果。 再分析题目其实就是一棵树支持添加和删除路径并支持单点询问，这就是树链剖分了。 因此我们随便以一个点为根，把树进行重链剖分加线段树维护。 由于题目要问的是不受某个点影响的最大重要度， 因此我们把每个线段树结点变成一个堆， 然后添加路径的时候把所有不在这条路径上的点所在的线段树结点的堆中加入这条路径的重要度， 因为这些点肯定不会影响这条路径的畅通。 那么直接O(N)的寻找所有不在这条路径上的点肯定会T那么我们采取更高效的办法： 在沿着重链向上跳的过程中，把所经过的重链的首尾记录下来排序之后把与之交错的区间加入线段树即可。 因为同一条重链在线段树中肯定是连续的。 问题在于题目还支持删除路径操作，那么怎么满足呢？ 再维护一个堆，删除时把重要度加入这个堆，求值时判断一下两个堆的堆顶元素， 若相同同时pop掉，否则加入堆的堆顶元素就是要求的值。（常规操作，证明很简单就略去了） 当然仅仅使用以上操作你不但会被T飞而且会被M飞。 那么问题出在哪呢？ 我们在用线段树求值的时候，一旦发现目标区间包含了当前区间那么当前区间所有值肯定会影响目标区间。 所以维护线段树时是不用下传和合并的。这样就节约了大量时间和空间。 经过层层优化终于可以AC了。 ```cpp #include<iostream> #include<vector> #include<queue> #include<cstring> #include<algorithm> using namespace std; struct opq { int ax; int ay; }kk[200001]; vector<int> a[200001]; priority_queue<int> segmenttree1[500001],segmenttree2[500001]; int n,m,size[200001],top[200001],position[200001]; int deep[200001],son[200001],fa[200001],z=0; int u[200001],v[200001],importance[200001]; bool cmp(opq a1,opq a2) { return a1.ax<a2.ax; } void dfs1(int o,int p) { size[o]=1; fa[o]=p; deep[o]=deep[p]+1; if(a[o].empty()) return; int maxx=0; for(int i=0;i<a[o].size();i++) if(a[o][i]!=fa[o]) { if(!size[a[o][i]]) dfs1(a[o][i],o); size[o]+=size[a[o][i]]; if(size[a[o][i]]>maxx) { maxx=size[a[o][i]]; son[o]=a[o][i]; } } } void dfs2(int o,int p) { z++; position[o]=z; top[o]=p; if(son[o]!=0) dfs2(son[o],top[o]); for(int i=0;i<a[o].size();i++) if((a[o][i]!=son[o])&&(a[o][i]!=fa[o])) dfs2(a[o][i],a[o][i]); } void put1(int o,int p,int q,int r,int s,int t)//加入堆的操作 { if(q>r) return; if((q>=o)&&(r<=p)) { segmenttree1[s].push(t); return; } int mid=(q+r)/2; if(p<=mid) put1(o,p,q,mid,s*2,t);else if(o>mid)put1(o,p,mid+1,r,s*2+1,t);else {put1(o,mid,q,mid,s*2,t);put1(mid+1,p,mid+1,r,s*2+1,t);} } void puttree1(int o,int p,int q)//加入堆的操作 { int yu=0; while(top[o]!=top[p]) { if(deep[top[o]]<deep[top[p]]){int t=o;o=p;p=t;} kk[++yu].ay=position[o]; kk[yu].ax=position[top[o]]; o=fa[top[o]]; } if(deep[o]>deep[p]){int t=o;o=p;p=t;} kk[++yu].ax=position[o]; kk[yu].ay=position[p]; sort(kk+1,kk+yu+1,cmp);//把所经过的重链的首尾记录下来排序 kk[0].ay=0; kk[++yu].ax=n+1; for(int i=1;i<=yu;i++) if(kk[i-1].ay+1<=kk[i].ax-1) put1(kk[i-1].ay+1,kk[i].ax-1,1,n,1,q);//把与之交错的区间加入线段树。 } void put2(int o,int p,int q,int r,int s,int t)//删除堆的操作 { if(q>r) return; if((q>=o)&&(r<=p)) { segmenttree2[s].push(t); return; } int mid=(q+r)/2; if(p<=mid) put2(o,p,q,mid,s*2,t);else if(o>mid)put2(o,p,mid+1,r,s*2+1,t);else {put2(o,mid,q,mid,s*2,t);put2(mid+1,p,mid+1,r,s*2+1,t);} } void puttree2(int o,int p,int q)//删除堆的操作 { int yu=0; while(top[o]!=top[p]) { if(deep[top[o]]<deep[top[p]]){int t=o;o=p;p=t;} kk[++yu].ay=position[o]; kk[yu].ax=position[top[o]]; o=fa[top[o]]; } if(deep[o]>deep[p]){int t=o;o=p;p=t;} kk[++yu].ax=position[o]; kk[yu].ay=position[p]; sort(kk+1,kk+yu+1,cmp); kk[0].ay=0; kk[++yu].ax=n+1; for(int i=1;i<=yu;i++) if(kk[i-1].ay+1<=kk[i].ax-1) put2(kk[i-1].ay+1,kk[i].ax-1,1,n,1,q); } int get(int o,int p,int q,int r,int s)//回答询问，求值。 { int xxx=-1; if((q<=o)&&(r>=p)) { while((!segmenttree1[s].empty())&&(!segmenttree2[s].empty())) { if(segmenttree1[s].top()!=segmenttree2[s].top())break; segmenttree1[s].pop(); segmenttree2[s].pop(); } if(!segmenttree1[s].empty()) xxx=segmenttree1[s].top(); } if(q==r) return xxx; int mid=(q+r)/2; if(p<=mid) return max(xxx,get(o,p,q,mid,s*2));else if(o>mid)return max(xxx,get(o,p,mid+1,r,s*2+1)); } int main() { cin>>n>>m; for(int i=1;i<n;i++) { int x,y; cin>>x>>y; a[x].push_back(y); a[y].push_back(x); } memset(son,0,sizeof(son)); memset(size,0,sizeof(size)); dfs1(1,0);//重链剖分第一次dfs，求出每个结点的重儿子父亲和以其为根的子树大小。 dfs2(1,1);//重链剖分第二次dfs，求出每个节点在线段树中的位置和所在重链的头。 for(int i=1;i<=m;i++) { int yu; cin>>yu; if(yu==0){cin>>u[i]>>v[i]>>importance[i];puttree1(u[i],v[i],importance[i]);} if(yu==1){cin>>u[i];puttree2(u[u[i]],v[u[i]],importance[u[i]]);} if(yu==2){cin>>u[i];cout<<get(position[u[i]],position[u[i]],1,n,1)<<endl;} } return 0; } ```