思路
提供一个不太一样的容斥做法。
首先容易发现答案只和每个点到 1 号点的奇偶最短路有关，可以先 \(O(n)\) 求出来。
然后考虑枚举距离 \(d\)，计算有多少个 K 元组的距离为 \(d\)。不妨设 \(d\) 为奇数，那么条件就是：
- 每个点的奇最短路的最大值为 \(d\)；
- 存在一个点的偶最短路 \(>d\)。
考虑怎么快速维护。对于每一张图，我们求出能到走到的奇偶最短路的最大值 \(maxd\)
我们把图分成两部分，一部分是 \(maxd<d\)，另一部分是 \(maxd\ge d\)。
对于第一部分，不存在满足第一个条件的点，而且对于所有 \(maxd<d\) 的 \(d\)，这张图的满足第二个条件的点数量不会变，贡献很好维护。
对于第二部分，我们遍历所有满足条件的图，维护 \(f[0/1][0/1]\) 表示是否满足第一个条件，是否满足第二个条件的方案数。我们需要知道对于每一张图，有多少个点满足奇最短路的为 \(d\)，有多少个点满足奇最短路的不超过 \(d\)，有多少个点满足奇最短路不超过 \(d\) 且偶最短路 \(>d\)，这些信息都可以 \(O(n+maxd)\) 求出。最终转移是一个或卷积。这一部分复杂度是 \(\sum maxd=O(\sum n)\) 的。
总复杂度 \(O(n)\)。
代码：
int K;
int p1[N<<1],p2[N<<1];
struct Graph{
int n,m,cnt,maxn;
vector<int>h,ver,nxt,dis[2],t,d,c,pre;
inline void add_edge(int x,int y){cnt++;ver[cnt]=y;nxt[cnt]=h[x];h[x]=cnt;}
inline void init(){
n=read(),m=read();
h.resize(n+1),ver.resize(2*m+1),nxt.resize(2*m+1),dis[0].resize(n+1),dis[1].resize(n+1);
for(int i=1;i<=n;i++)dis[0][i]=dis[1][i]=mod;
for(int i=1;i<=m;i++){
int x=read(),y=read();
add_edge(x,y),add_edge(y,x);
}
queue<int>q;
dis[0][1]=0;
q.push(2);
while(!q.empty()){
int x=q.front()>>1,k=q.front()&1;
q.pop();
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(dis[k^1][y]>dis[k][x]+1){
dis[k^1][y]=dis[k][x]+1;
q.push((y<<1)|(k^1));
}
}
}
for(int i=1;i<=n;i++){
if(dis[0][i]!=mod)maxn=max(maxn,dis[0][i]);
if(dis[1][i]!=mod)maxn=max(maxn,dis[1][i]);
}
t.resize(maxn+1),d.resize(maxn+1),c.resize(maxn+3),pre.resize(maxn+1);
for(int i=1;i<=n;i++){
if(dis[0][i]<dis[1][i]){
d[dis[0][i]]++;
c[dis[0][i]]++;
if(dis[1][i]!=mod)c[dis[1][i]+1]--;
}
if(dis[1][i]<dis[0][i]){
d[dis[1][i]]++;
c[dis[1][i]]++;
if(dis[0][i]!=mod)c[dis[0][i]+1]--;
}
if(dis[0][i]!=mod)t[dis[0][i]]++;
if(dis[1][i]!=mod)t[dis[1][i]]++;
}
for(int i=0;i<=maxn;i++){
pre[i]=t[i];
if(i>1)pre[i]+=pre[i-2];
}
for(int i=2;i<=maxn+2;i++)c[i]+=c[i-2];
p1[maxn+2]=1ll*p1[maxn+2]*pre[maxn]%mod;
p2[maxn+2]=1ll*p2[maxn+2]*dec(pre[maxn],c[maxn+2])%mod;
p1[maxn+1]=1ll*p1[maxn+1]*(maxn?pre[maxn-1]:0)%mod;
p2[maxn+1]=1ll*p2[maxn+1]*dec(maxn?pre[maxn-1]:0,c[maxn+1])%mod;
}
}G[N];
vector<int>hav[N],q;
int maxd;
int f[4],g[4],a[4],ans;
int main(){
K=read();
for(int i=0;i<=200003;i++)p1[i]=p2[i]=1;
for(int i=1;i<=K;i++){
G[i].init();
hav[G[i].maxn].push_back(i);
maxd=max(maxd,G[i].maxn);
}
for(int i=2;i<=maxd;i++)p1[i]=1ll*p1[i]*p1[i-2]%mod,p2[i]=1ll*p2[i]*p2[i-2]%mod;
for(int i=maxd;i;i--){
for(auto j:hav[i])q.push_back(j);
memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
g[0]=p2[i];g[1]=dec(p1[i],p2[i]);
for(auto j:q){
a[0]=G[j].pre[i]-G[j].t[i]-G[j].c[i]+G[j].d[i],a[1]=G[j].c[i]-G[j].d[i],a[2]=G[j].t[i]-G[j].d[i],a[3]=G[j].d[i];
memset(f,0,sizeof(f));
for(int i=0;i<4;i++){
for(int j=0;j<4;j++)add(f[i|j],1ll*g[i]*a[j]%mod);
}
swap(f,g);
}
add(ans,1ll*g[3]*i%mod);
}
cout<<ans<<endl;
return 0;
}