「USACO 2021.1 Platinum」Sum of Distances

设在$G_i$中$j_i$点可行的距离集合为$D_{j_i}$

注意到一个点的$(j_1,j_2,\ldots,j_k)$的$dis$可以用如下方式确定

$\displaystyle dis(j_1,j_2,\ldots,j_k)=\min\{\bigcap D_{j_i} \}$

而$D_{j_i}$有一个简单的描述方法：

求出奇数和偶数的最小值，然后再最小值往上+$2k$的部分均存在（不停来回）

这样我们用两个值$odd_{j_i},even_{j_i}$描述了$D_{j_i}$

同时也容易得到$\displaystyle dis(j_1,j_2,\ldots,j_k)=\min\{\max\{odd_{j_i} \},\max\{even_{j_i} \} \}$

也就是说要在奇偶的$\max$之间取$\min$

考虑$odd_{j_i},even_{j_i}$是$O(N_i)$级别的，可以暴力合并，但是无法处理外层的$\min$，因此考虑用一个简单的$\text{minmax}$容斥解决

$\min\{a,b\}=a+b-\max\{a,b\}$

这样就只有$\max$要计算了，用简单的前缀和优化取$\max$操作

注意要按照$N_i$排序之后依次合并每一个$G_i$保证复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
typedef pair <int,int> Pii;
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
int rd(){
	int s=0;
	while(!isdigit(IO=getchar()));
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return s;
}

const int N=2e5+10,P=1e9+7;

int n;
int C[N],R[N],D[N][2],I[N],M[N],S[N*2];
vector <int> G[N];
int dis[N][2],U,F[N],H[N];

int Solve(int S){
	F[U=0]=1;
	rep(k,1,n) {
		int i=I[k];
		rep(j,U+1,M[i]) F[j]=F[j-1];
		cmax(U,M[i]);
		rep(j,0,U) H[j]=0;
		rep(j,R[i-1]+1,R[i]) {
			int d=-1;
			if(S&1) cmax(d,D[j][0]);
			if(S&2) cmax(d,D[j][1]);
			if(d==P) continue;
			H[d]++;
		}
		rep(j,1,U) H[j]+=H[j-1];
		rep(j,0,U) F[j]=1ll*F[j]*H[j]%P;
	}
	drep(j,U,1) F[j]-=F[j-1],Mod2(F[j]);
	int ans=0;
	rep(j,0,U) ans=(ans+1ll*j*F[j])%P;
	return ans;
}

int main(){
	n=rd();
	rep(i,1,n) {
		I[i]=i,C[i]=rd(),R[i]=R[i-1]+C[i];
		rep(j,1,C[i]) G[j].clear();
		rep(j,1,rd()){
			int u=rd(),v=rd();
			G[u].pb(v),G[v].pb(u);
		}
		rep(j,1,C[i]) dis[j][0]=dis[j][1]=P;
		dis[1][0]=0;
		static queue <Pii> que; que.push(mp(1,0));
		while(!que.empty()){
			int u=que.front().first,d=que.front().second; que.pop();
			cmax(M[i],dis[u][d]);
			for(int v:G[u]) if(dis[v][!d]>dis[u][d]+1) dis[v][!d]=dis[u][d]+1,que.push(mp(v,!d));
		}
		rep(j,1,C[i]) {
			rep(k,0,1) {
				D[R[i-1]+j][k]=dis[j][k];
				if(dis[j][k]!=P) cmax(M[i],dis[j][k]);
			}
		}
	}
	sort(I+1,I+n+1,[&](int x,int y){ return C[x]<C[y]; });
	int ans=((Solve(1)+Solve(2)-Solve(3))%P+P)%P;
	printf("%d\n",ans);
}