题解——线性作法（求赞）

简单的线性做法。

从新图的起点走到 (a
1
​
,a
2
​
...a
k
​
)，相当于在 k 张图上同时从 1 走到 a
i
​
。

如果某张图比其他图先走到，那么这个点可以任选一条经过它的边反复横跳。

所以只需要保证每张图上从 1 走到 a
i
​
距离的奇偶性相同。

首先通过 bfs，预处理每张图上 1 到所有点的长度为奇数和偶数的最短路。

记 ji
i
​
为奇数最短路，ou
i
​
为偶数最短路，若不存在则为 inf。

则新图的起点到 (a
1
​
,a
2
​
...a
k
​
) 的距离，等于 min(max(ji
a
i
​

​
),max(ou
a
i
​

​
))。

这个式子不好处理，通过 a+b=min(a,b)+max(a,b)，转化为 max(ji
a
i
​

​
)+max(ou
a
i
​

​
)−max(max(ji
a
i
​

​
,ou
a
i
​

​
))。

将三部分分别计算，每次分别记 w
i
​
=ji
i
​
,ou
i
​
,max(ji
i
​
,ou
i
​
)。

考虑对于每个点 j，求出 j∈a
i
​
，且 w
j
​
=max(w
a
i
​

​
) 的方案数。

发现这样会算重，考虑对于相同的 w
j
​
，按所属图的编号为第二关键字比较。

于是只需要将所有点按 w
j
​
为第一关键字，图的编号为第二关键字排序，因为值域是点数级别，所以这部分复杂度是线性。

然后按顺序依次加入每个点，加入属于图 k 的点 j 时的方案数，就是除 k 以外所有图已经被加入的点的个数的乘积。

预处理乘法逆元可以 O(1) 加点。

总复杂度线性。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3,P=1e9+7;
basic_string<int>v[3][N+1];
int iv[N],a[N],o,u;
void in(){
int n,m,i,j;
basic_string<int>ji,ou;
vector<basic_string<int>>g;
queue<int>q;
scanf("%d%d",&n,&m),ji.assign(n+1,N),ou.assign(n+1,N),g.resize(n+1);
while(m--)scanf("%d%d",&i,&j),g[i]+=j,g[j]+=i;
q.push(1),ou[1]=0;
while(q.size()){//bfs
i=q.front(),q.pop();
if(i>n){
i-=n;
for(int j:g[i])if(ou[j]==N)ou[j]=ji[i]+1,q.push(j);
}else for(int j:g[i])if(ji[j]N)ji[j]=ou[i]+1,q.push(j+n);
}
for(i=1;i<=n;++i)v[0][ji[i]]+=u,v[1][ou[i]]+=u,v[2][max(ji[i],ou[i])]+=u;
}
int get(basic_string<int>v){
int i,s=0,t=1,c=0;
for(i=0,memset(a,0,N4);i<N;++i)for(int j:v[i]){//加点
if(a[j])t=t1lliv[a[j]]%P;else ++c;
if(co)s=(s+t1lli)%P;
t=t1ll(++a[j])%P;
}
return s;
}
int main(){
for(iv[1]=1,u=2;u<N;++u)iv[u]=(P-P/u)1lliv[P%u]%P;//预处理逆元
for(scanf("%d",&o),u=1;u<=o;++u)in();
printf("%d",((get(v[0])+get(v[1])-get(v[2]))%P+P)%P);
return 0;
}