题目描述
在 H 国的小 w 决定到从城市 (u) 到城市 (v) 旅行，但是此时小 c 由于各种原因不在城市 (u)，但是小 c 决定到在中途与小 w 相遇
由于 H 国道路的原因，小 w 从城市 (u) 到城市 (v) 的路线不是固定的，为了合理分配时间，小 c 想知道从城市 (u) 到城市 (v) 有多少个城市小 w 一定会经过，特别地，(u,v) 也必须被算进去，也就是说无论如何答案不会小于 2
由于各种特殊的原因，小 c 并不知道小 w 的起点和终点，但是小 c 知道小 w 的起点和终点只有 (M) 种可能，所以对于这 (M) 种可能，小 c 都想知道小 w 一定会经过的城市数
H 国所有的边都是无向边，两个城市之间最多只有一条道路直接相连，没有一条道路连接相同的一个城市
任何时候，H 国不存在城市 (u) 和城市 (v) 满足从 (u) 无法到达 (v)
输入输出格式
输入格式：
输入第 1 行两个正整数 (N,E)，表示 H 国的城市数，以及道路数
输入第 2 行至第 (E+1) 行，每行两个不同的正整数 (u,v)，表示城市 (u) 到城市 (v) 之间有一条边
输入第 (E+2) 行一个正整数 (M)
输入第 (E+3) 行到第 (E+M+2) 行每行两个正整数 (u,v) 表示小 w 旅行的一种可能的路线
输出格式：
输出共 (M) 行，每行一个正整数
输入输出样例
输入样例#1：
5 6
1 2
1 3
2 3
3 4
4 5
3 5
1
1 5
输出样例#1：
3
说明
从城市 1 到城市 5 总共有 4 种可能 :
1 -> 2 -> 3 -> 4 -> 5
1 -> 2 -> 3 -> 5
1 -> 3 -> 4 -> 5
1 -> 3 -> 5
可以发现小 w 总会经过城市 1, 3, 5，所以答案为 3
你可以认为小 w 不会经过相同的城市两次，当然，如果你认为可以经过相同的城市两次也不会影响答案
subtask1 : 15分，(N=5,M=50)
subtask2 : 15分，(N=100,M=5000)
subtask3 : 20分，(N=3000,M=500000)
subtask4 : 20分，(N=499999,M=500000,E=N−1)
subtask5 : 30分，(N=500000,M=500000)
对于所有数据 : (1leq Nleq 500000, 1leq Mleq 500000, 1leq Eleq min(frac{N(N-1)}{2}, 1000000))
题解
建出圆方树，题目所求的就是 (u) 到 (v) 的路径上有多少圆点
树上差分一下就好了
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=1000000+10;
int n,k,m,e,cnt,val[MAXN],beg[MAXN],nex[MAXN<<1],to[MAXN<<1],out[MAXN<<1],DFN[MAXN],LOW[MAXN],Visit_Num,vis[MAXN],d[MAXN],dep[MAXN],Jie[20][MAXN],s[MAXN<<1],top;
std::vector<int> point[MAXN];
namespace IO
{
const ui Buffsize=1<<15,Output=1<<23;
static char Ch[Buffsize],*S=Ch,*T=Ch;
inline char getc()
{
return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
}
static char Out[Output],*nowps=Out;
inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}
template<typename T>inline void read(T&x)
{
x=0;static char ch;T f=1;
for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getc())x=(x<<3)+(x<<1)+(ch^'0');
x*=f;
}
template<typename T>inline void write(T x,char ch='
')
{
if(!x)*nowps++='0';
if(x<0)*nowps++='-',x=-x;
static ui sta[111],tp;
for(tp=0;x;x/=10)sta[++tp]=x%10;
for(;tp;*nowps++=sta[tp--]^48);
*nowps++=ch;
}
}
using namespace IO;
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void insert(int x,int y)
{
to[++e]=y;
nex[e]=beg[x];
out[e]=x;
beg[x]=e;
}
inline void Tarjan(int x,int f)
{
DFN[x]=LOW[x]=++Visit_Num;
for(register int i=beg[x];i;i=nex[i])
if(to[i]==f)continue;
else if(!DFN[to[i]])
{
s[++top]=i;
Tarjan(to[i],x);
chkmin(LOW[x],LOW[to[i]]);
if(LOW[to[i]]>=DFN[x])
{
static int temp;++cnt;
do{
temp=s[top--];
if(vis[out[temp]]!=cnt)
{
vis[out[temp]]=cnt;
point[cnt].push_back(out[temp]);
}
if(vis[to[temp]]!=cnt)
{
vis[to[temp]]=cnt;
point[cnt].push_back(to[temp]);
}
}while(out[temp]!=x||to[temp]!=to[i]);
}
}
else if(DFN[to[i]]<DFN[x])s[++top]=i,chkmin(LOW[x],DFN[to[i]]);
}
inline void dfs(int x,int f)
{
d[x]=d[f]+val[x];Jie[0][x]=f;dep[x]=dep[f]+1;
for(register int i=beg[x];i;i=nex[i])
if(to[i]!=f)dfs(to[i],x);
}
inline int LCA(int u,int v)
{
if(dep[u]<dep[v])std::swap(u,v);
int tmp=dep[u]-dep[v];
for(register int i=19;i>=0;--i)
if(tmp>>i&1)u=Jie[i][u];
if(u==v)return u;
for(register int i=19;i>=0;--i)
if(Jie[i][u]^Jie[i][v])u=Jie[i][u],v=Jie[i][v];
return Jie[0][u];
}
int main()
{
read(n);read(k);
for(register int i=1;i<=k;++i)
{
int u,v;read(u);read(v);
insert(u,v);insert(v,u);
}
Tarjan(1,0);e=0;
for(register int i=1;i<=n;++i)val[i]=1,beg[i]=0;
for(register int i=1;i<=cnt;++i)
for(register int j=0,lt=point[i].size();j<lt;++j)insert(i+n,point[i][j]),insert(point[i][j],i+n);
dfs(1,0);
for(register int j=1;j<20;++j)
for(register int i=1;i<=n+cnt;++i)Jie[j][i]=Jie[j-1][Jie[j-1][i]];
read(m);
static int u,v,lca;
while(m--)
{
read(u);read(v);lca=LCA(u,v);
write(d[u]+d[v]-d[lca]-d[Jie[0][lca]],'
');
}
flush();
return 0;
}