P3250 [HNOI2016]网络题解

题面

一个显然的做法是树剖之后dfs序线段树套时间线段树，直接做的复杂度是 \(O(n\log^3 n)\)。其实也可以把询问离线下来，做一个线段树分治，用树套树维护。

这样做比较麻烦，所以考虑另外一种思路：二分答案。因为有很多询问，不妨放在一起二分，所以可以想到整体二分。使用类似树上差分的思想，对于一条路径 \(u\rightarrow lca(u,v)\to v\)，如果它的权值大于 \(mid\)，在用dfs序建的树状数组上给 \(u,v\) 加一，给 \(lca\) 和 \(fa[lca]\) 减一，对于询问统计经过该点的路径条数是否等于此时权值大于 \(mid\) 的路径数量，向两边递归即可。

这道题还有使用路径交等一系列科技的 \(1\log\) 做法，太神了本人（当时可能）并不会……然而现在估计也不会。

点击查看代码

#include<iostream>#include<cstdio>#include<algorithm>inline int max(const int &a,const int &b){return a>b?a:b;}inline void swap(int &x,int &y){x^=y^=x^=y;}inline int rd(){int res=0;char c=getchar();for(;!isdigit(c);c=getchar());for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');return res;}void wt(int x){if(x<0){putchar('-'),wt(-x);return;}if(x>9)wt(x/10);putchar(x%10+'0');}const int N=2e5+13;struct Node{int op,u,v,t,x,id,ans;bool operator <(const Node &a)const{return id<a.id;}}q[N],lq[N],rq[N];struct Edge{int v,nxt;}e[N<<1];int n,m,h[N],tot;struct BIT{int t[N];#define lowbit(x) (x&-x)inline void add(int x,int k){for(;x<=2*n;x+=lowbit(x))t[x]+=k;}inline int sum(int x){int s=0;for(;x;x-=lowbit(x))s+=t[x];return s;}#undef lowbit}T;int dfnl[N],dfnr[N],dfs_clock;int fa[N],dep[N],siz[N],son[N],top[N];inline void add_edge(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}void dfs1(int u,int f,int deep){dfnl[u]=++dfs_clock,fa[u]=f,dep[u]=deep,siz[u]=1;int maxson=0;for(int i=h[u];i;i=e[i].nxt){int v=e[i].v;if(v==f) continue;dfs1(v,u,deep+1);siz[u]+=siz[v];if(siz[v]>maxson) maxson=siz[v],son[u]=v;}dfnr[u]=++dfs_clock;}void dfs2(int u,int topf){top[u]=topf;if(!son[u]) return;dfs2(son[u],topf);for(int i=h[u];i;i=e[i].nxt){int v=e[i].v;if(v!=fa[u]&&v!=son[u]) dfs2(v,v);}}inline int lca(int u,int v){while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]) swap(u,v);u=fa[top[u]];}return dep[u]<dep[v]?u:v;}void solve(int L,int R,int l,int r){if(l>r) return;if(L==R){for(int i=l;i<=r;++i)if(q[i].op==2) q[i].ans=L;return;}int mid=(L+R)>>1,lt=0,rt=0,tmp=0;for(int i=l;i<=r;++i){if(q[i].op!=2){if(q[i].x<=mid) lq[++lt]=q[i];else{int v=(q[i].op?-1:1);tmp+=v;if(q[i].u&&q[i].v) T.add(dfnl[q[i].u],v),T.add(dfnl[q[i].v],v),T.add(dfnl[q[i].t],-v);if(fa[q[i].t]) T.add(dfnl[fa[q[i].t]],-v);rq[++rt]=q[i];}}else{if(T.sum(dfnr[q[i].x])-T.sum(dfnl[q[i].x]-1)==tmp) lq[++lt]=q[i];else rq[++rt]=q[i];}}for(int i=l;i<=r;++i){if(q[i].op==2||q[i].x<=mid) continue;int v=(q[i].op?1:-1);T.add(dfnl[q[i].u],v),T.add(dfnl[q[i].v],v),T.add(dfnl[q[i].t],-v);if(fa[q[i].t]) T.add(dfnl[fa[q[i].t]],-v);}for(int i=1;i<=lt;++i) q[l+i-1]=lq[i];for(int i=1;i<=rt;++i) q[l+lt+i-1]=rq[i];solve(L,mid,l,l+lt-1);solve(mid+1,R,l+lt,r);}int main(){n=rd(),m=rd();for(int i=1,u,v;i<n;++i) u=rd(),v=rd(),add_edge(u,v),add_edge(v,u);dfs1(1,0,0);dfs2(1,1);int lim=0;for(int i=1,type,u,v,x;i<=m;++i){q[i].op=rd(),q[i].id=i;if(!q[i].op){q[i].u=rd(),q[i].v=rd(),q[i].x=rd();lim=max(lim,q[i].x);q[i].t=lca(q[i].u,q[i].v);}else if(q[i].op==1){int k=rd();q[i]=q[k],q[i].op=1;}else q[i].x=rd();}solve(0,lim,1,m);std::sort(q+1,q+m+1);for(int i=1;i<=m;++i)if(q[i].op==2) wt(q[i].ans?q[i].ans:-1),putchar('\n');return 0;}

标签：网络题解技巧

免责声明：本网信息来自于互联网，目的在于传递更多信息，并不代表本网赞同其观点。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，并请自行核实相关内容。本站不承担此类作品侵权行为的直接责任及连带责任。如若本网有任何内容侵犯您的权益，请及时联系我们，本站将会在24小时内处理完毕。