Sum of Distances USACO 2021 January Contest

Sum of Distances USACO Solution Bessie has a collection of connected, undirected graphs G1,G2,…,GKG1,G2,…,GK (2≤K≤5⋅1042≤K≤5⋅104). For each 1≤i≤K1≤i≤K, GiGi has exactly NiNi (Ni≥2Ni≥2) vertices labeled 1…Ni1…Ni and MiMi (Mi≥Ni−1Mi≥Ni−1) edges. Each GiGi may contain self-loops, but not multiple edges between the same pair of vertices. See Also: USACO 2021 January Contest Now Elsie creates a new undirected graph GG with N1⋅N2⋯NKN1⋅N2⋯NK vertices, each labeled by a KK-tuple (j1,j2,…,jK)(j1,j2,…,jK) where 1≤ji≤Ni1≤ji≤Ni. In GG, two vertices (j1,j2,…,jK)(j1,j2,…,jK) and (k1,k2,…,kK)(k1,k2,…,kK) are connected by an … Read more