本文主要是介绍[ONTAK2010]Highways，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
想学线段树合并找的一个题。。没想到是个傻逼题。
这题题意好像有问题：额外的点对和查询的点对都不会是同一个点。
设x的dfs序为dfn(x)，x的子树中dfs序最大的节点的dfs序为dr(x)。将额外的边(u,v)看作点 (dfn(u),dfn(v))(dfn(u)≤dfn(v)) 。对于一次查询 (u,v)(dfn(u)≤dfn(v)) ，如果lca(u,v)==u，那么就找到v的一个祖先x使得fa(x)=u，然后就相当于询问矩形[dfn(v),dr(v)]-[1,dfn(x)-1]+[dfn(v),dr(v)]-[dr(x)+1,n]矩形中点的个数；如果lca(u,v)!=v，那么就相当于询问[dfn(v),dr(v)]-[dfn(u),dr(u)]中点的个数。所以就是平面上有一些点，然后每次询问一个矩形中有多少点。。就成了noip难度的题了。。
一个非常直观的想法就是扫描线+bit，把每个矩形拆成两次询问。这样做的时间复杂度是 O(n+(m+q)log2n) 。如果要求在线的话就换成主席树就可以了。
但是我为什么要为这样一道水题写解题报告呢？——因为注意到m与q不同阶，所以又到了喜闻乐见的分块大战bit的时候了！我们实际上面临 105 次插入和 2∗106 次查询，所以如果我们分块，时间复杂度 O(n+mn√+q) ！
能不能跑过bit呢？答案当然还是一如既往的。。并不能。。
代码（bit）：
#include<cstdio>
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
#include<cmath>
const int N=1e5+5,M=1e5+5,Q=5e5+5;
int n;char * cp=(char *)malloc(10000000);
void in(int &x){while(*cp<'0'||*cp>'9')++cp;for(x=0;*cp>='0'&&*cp<='9';)x=x*10+(*cp++^'0');
}
char * os=(char *)malloc(4000000),* op=os;
void out(int x){if(x){out(x/10);*op++='0'+x%10;}
}int next[N<<1],succ[N<<1],ptr[N],etot=1;
void addedge(int from,int to){next[etot]=ptr[from],ptr[from]=etot,succ[etot++]=to;
}
int dfn[N],dr[N],dtot=1;
const int Log=17;
int top[N],size[N],fa[N];
void sizedfs(int node){size[node]=1;for(int i=ptr[node];i;i=next[i])if(succ[i]!=fa[node]){fa[succ[i]]=node;sizedfs(succ[i]);size[node]+=size[succ[i]];}
}
void builddfs(int node){//printf("%d ",node);dfn[node]=dtot++;if(!top[node])top[node]=node;int bigson=0;for(int i=ptr[node];i;i=next[i])if(fa[node]!=succ[i]&&size[succ[i]]>size[bigson])bigson=succ[i];if(bigson){builddfs(bigson);for(int i=ptr[node];i;i=next[i])if(fa[node]!=succ[i]&&bigson!=succ[i])builddfs(succ[i]);}dr[dfn[node]]=dtot-1;
}int bit[N];
void add(int x){for(;x<=n;x+=x&-x)++bit[x];
}
int query(int x){int ans=0;for(;x;x-=x&-x)ans+=bit[x];return ans;
}struct PS{int x,y;//x>=ybool operator < (const PS & o)const{return x<o.x;}
}point[M];struct QS{int x,yl,yr;int coe;int i;bool operator < (const QS & o)const{return x<o.x;}
}que[Q<<2];
int qtot;
int ans[Q];int main(){freopen("bzoj_3488.in","r",stdin);freopen("bzoj_3488_bit.out","w",stdout);fread(cp,1,10000000,stdin);in(n);int u,v;for(int i=n;--i;){in(u),in(v);addedge(u,v),addedge(v,u);}sizedfs(1);builddfs(1);//puts("");int m;in(m);for(int i=m;i--;){in(point[i].x),in(point[i].y);if((point[i].x=dfn[point[i].x])<(point[i].y=dfn[point[i].y]))swap(point[i].x,point[i].y);//printf("(%d,%d)\n",point[i].x,point[i].y);}int q;in(q);for(int i=0;i<q;++i)ans[i]=1;int x;for(int i=0;i<q;++i){in(u),in(v);if(dfn[u]>dfn[v])swap(u,v);//printf("(%d,%d):",u,v);if(dr[dfn[u]]>=dr[dfn[v]]){if(dr[dfn[u]+1]>=dr[dfn[v]])x=dfn[u]+1;else{x=v;while(fa[top[x]]!=u)x=fa[top[x]];x=dfn[x];}//printf("%d\n",x);que[qtot++]=(QS){dfn[v]-1,1,x-1,-1,i};que[qtot++]=(QS){dr[dfn[v]],1,x-1,1,i};que[qtot++]=(QS){dr[x],dfn[v],dr[dfn[v]],-1,i};que[qtot++]=(QS){n,dfn[v],dr[dfn[v]],1,i};}else{//puts("Two subtree");que[qtot++]=(QS){dfn[v]-1,dfn[u],dr[dfn[u]],-1,i};que[qtot++]=(QS){dr[dfn[v]],dfn[u],dr[dfn[u]],1,i};}}sort(point,point+m),sort(que,que+qtot);for(int i=1,j=0,k=0;i<=n;++i){for(;point[j].x==i;++j)add(point[j].y);for(;que[k].x==i;++k)ans[que[k].i]+=que[k].coe*(query(que[k].yr)-query(que[k].yl-1));}for(int i=0;i<q;++i){if(ans[i])out(ans[i]);else *op++='0';*op++='\n';}fwrite(os,1,op-os,stdout);
}代码（分块）：
#include<cstdio>
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
#include<cmath>
const int N=1e5+5,M=1e5+5,Q=5e5+5;
int n;char * cp=(char *)malloc(10000000);
void in(int &x){while(*cp<'0'||*cp>'9')++cp;for(x=0;*cp>='0'&&*cp<='9';)x=x*10+(*cp++^'0');
}
char * os=(char *)malloc(4000000),* op=os;
void out(int x){if(x){out(x/10);*op++='0'+x%10;}
}int next[N<<1],succ[N<<1],ptr[N],etot=1;
void addedge(int from,int to){next[etot]=ptr[from],ptr[from]=etot,succ[etot++]=to;
}
int dfn[N],dr[N],dtot=1;
const int Log=17;
int top[N],size[N],fa[N];
void sizedfs(int node){size[node]=1;for(int i=ptr[node];i;i=next[i])if(succ[i]!=fa[node]){fa[succ[i]]=node;sizedfs(succ[i]);size[node]+=size[succ[i]];}
}
void builddfs(int node){//printf("%d ",node);dfn[node]=dtot++;if(!top[node])top[node]=node;int bigson=0;for(int i=ptr[node];i;i=next[i])if(fa[node]!=succ[i]&&size[succ[i]]>size[bigson])bigson=succ[i];if(bigson){builddfs(bigson);for(int i=ptr[node];i;i=next[i])if(fa[node]!=succ[i]&&bigson!=succ[i])builddfs(succ[i]);}dr[dfn[node]]=dtot-1;
}const int B=320;
int bs[505],s[505][505];
void add(int x){for(int i=x/B;i<=n/B;++i)++bs[i+1];for(int j=x%B+1;j<=B;++j)++s[x/B+1][j];
}
int query(int x){return bs[x/B]+s[x/B+1][x%B+1];
}struct PS{int x,y;//x>=ybool operator < (const PS & o)const{return x<o.x;}
}point[M];struct QS{int x,yl,yr;int coe;int i;bool operator < (const QS & o)const{return x<o.x;}
}que[Q<<2];
int qtot;
int ans[Q];int main(){freopen("bzoj_3488.in","r",stdin);freopen("bzoj_3488.out","w",stdout);fread(cp,1,10000000,stdin);in(n);int u,v;for(int i=n;--i;){in(u),in(v);addedge(u,v),addedge(v,u);}sizedfs(1);builddfs(1);//puts("");int m;in(m);for(int i=m;i--;){in(point[i].x),in(point[i].y);if((point[i].x=dfn[point[i].x])<(point[i].y=dfn[point[i].y]))swap(point[i].x,point[i].y);//printf("(%d,%d)\n",point[i].x,point[i].y);}int q;in(q);for(int i=0;i<q;++i)ans[i]=1;int x;for(int i=0;i<q;++i){in(u),in(v);if(dfn[u]>dfn[v])swap(u,v);//printf("(%d,%d):",u,v);if(dr[dfn[u]]>=dr[dfn[v]]){if(dr[dfn[u]+1]>=dr[dfn[v]])x=dfn[u]+1;else{x=v;while(fa[top[x]]!=u)x=fa[top[x]];x=dfn[x];}//printf("%d\n",x);que[qtot++]=(QS){dfn[v]-1,1,x-1,-1,i};que[qtot++]=(QS){dr[dfn[v]],1,x-1,1,i};que[qtot++]=(QS){dr[x],dfn[v],dr[dfn[v]],-1,i};que[qtot++]=(QS){n,dfn[v],dr[dfn[v]],1,i};}else{//puts("Two subtree");que[qtot++]=(QS){dfn[v]-1,dfn[u],dr[dfn[u]],-1,i};que[qtot++]=(QS){dr[dfn[v]],dfn[u],dr[dfn[u]],1,i};}}sort(point,point+m),sort(que,que+qtot);for(int i=1,j=0,k=0;i<=n;++i){for(;point[j].x==i;++j)add(point[j].y);for(;que[k].x==i;++k)ans[que[k].i]+=que[k].coe*(query(que[k].yr)-query(que[k].yl-1));}for(int i=0;i<q;++i){if(ans[i])out(ans[i]);else *op++='0';*op++='\n';}fwrite(os,1,op-os,stdout);
}总结：
①bit的常数确实比分块小。
这篇关于[ONTAK2010]Highways的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
