「USACO 2021.1 Platinum」Sum of Distances

「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{igcap 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)，因此考虑用一个简单的( ext{minmax})容斥解决

(min{a,b}=a+b-max{a,b})

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

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

#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
",ans);
}