#852179 (Go) No.1326 ふたりのDominator

• 問題: No.1326 ふたりのDominator
• ユーザー: 草苺奶昔
• 提出日時: 2023-03-24 14:27:11
• 言語: Go (1.22.1)
• 結果: AC
• 実行時間: 371 ms / 2,000 ms
• コード長: 13,564 bytes
• コンパイル時間: 15,846 ms
• コンパイル使用メモリ: 215,940 KB
• 実行使用メモリ: 74,820 KB
• 最終ジャッジ日時: 2023-10-18 20:27:19
• 合計ジャッジ時間: 22,604 ms
• ジャッジサーバーID （参考情報）: judge15 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,348 KB
testcase_01	AC	1 ms; 4,348 KB
testcase_02	AC	1 ms; 4,348 KB
testcase_03	AC	2 ms; 4,348 KB
testcase_04	AC	2 ms; 4,348 KB
testcase_05	AC	2 ms; 4,348 KB
testcase_06	AC	2 ms; 4,348 KB
testcase_07	AC	3 ms; 4,348 KB
testcase_08	AC	3 ms; 4,348 KB
testcase_09	AC	4 ms; 4,348 KB
testcase_10	AC	4 ms; 4,348 KB
testcase_11	AC	4 ms; 4,348 KB
testcase_12	AC	273 ms; 29,312 KB
testcase_13	AC	268 ms; 29,304 KB
testcase_14	AC	268 ms; 29,324 KB
testcase_15	AC	284 ms; 29,340 KB
testcase_16	AC	268 ms; 29,316 KB
testcase_17	AC	256 ms; 31,384 KB
testcase_18	AC	308 ms; 45,708 KB
testcase_19	AC	231 ms; 33,200 KB
testcase_20	AC	295 ms; 58,024 KB
testcase_21	AC	294 ms; 59,696 KB
testcase_22	AC	371 ms; 74,820 KB
testcase_23	AC	220 ms; 25,044 KB
testcase_24	AC	271 ms; 29,312 KB

ソースコード

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	yukicode1326()
}

func 从BlockCutTree还原点双连通分量() {
	// https://judge.yosupo.jp/problem/biconnected_components
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m int
	fmt.Fscan(in, &n, &m)
	graph := make([][]Edge, n)
	for i := 0; i < m; i++ {
		var u, v int
		fmt.Fscan(in, &u, &v)
		graph[u] = append(graph[u], Edge{u, v, 1, i})
		graph[v] = append(graph[v], Edge{v, u, 1, i})
	}
	B := NewBlockCutTree(graph)
	B.Build()

	tree := B.Tree
	vbccSize := len(tree) - B.CountCut()
	group := make([][]int, vbccSize, n)
	for i := 0; i < n; i++ {
		if B.IsRawIsolate(i) { // 孤立点特殊处理，作为一组
			group = append(group, []int{i})
			continue
		}
		if B.IsRawCut(i) {
			for _, v := range tree[B.Get(i)] {
				group[v] = append(group[v], i)
			}
		} else {
			group[B.Get(i)] = append(group[B.Get(i)], i)
		}
	}

	fmt.Fprintln(out, len(group))
	for i := 0; i < len(group); i++ {
		fmt.Fprint(out, len(group[i]))
		for _, v := range group[i] {
			fmt.Fprint(out, " ", v)
		}
		fmt.Fprintln(out)
	}
}

func 网络集群() {
	// https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3022
	// 给定一个`无向连通图`
	// 网络连接,对一个网络集群维修,每天维修一台机器,需要断开它和其他机器的连接
	// !对每个顶点,移除他连接的所有边后,求剩下的连通分量的权值和的最大值(総合性能値)
	// BlockCutTree上dp
	// 如果i不是割点的话,就是原图中的所有点的权值和减去这个点的权值
	// 如果i是割点的话,就是max(子树和,allSum-子树和-这个点的权值)

	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m int
	fmt.Fscan(in, &n, &m)
	values := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &values[i])
	}

	rawGraph := make([][]Edge, n)
	for i := 0; i < m; i++ {
		var u, v int
		fmt.Fscan(in, &u, &v)
		u--
		v--
		rawGraph[u] = append(rawGraph[u], Edge{u, v, 1, i})
		rawGraph[v] = append(rawGraph[v], Edge{v, u, 1, i})
	}

	B := NewBlockCutTree(rawGraph)
	B.Build()

	tree := B.Tree
	weight := make([]int, len(tree)) // 每个BlockCutTree的顶点的权值和
	all := 0
	for i := 0; i < n; i++ {
		weight[B.Get(i)] += values[i]
		all += values[i]
	}

	res := make([]int, n)
	for i := 0; i < n; i++ {
		if !B.IsRawCut(i) {
			res[i] = all - values[i] // 如果i不是割点的话,就是原图中的所有点的权值和减去这个点的权值
		}
	}

	var dfs func(cur, parent int) int
	dfs = func(cur, parent int) int {
		max_, sum := 0, 0
		for _, next := range tree[cur] {
			if next == parent {
				continue
			}
			nextRes := dfs(next, cur)
			sum += nextRes
			max_ = max(max_, nextRes)
		}
		if B.IsNewCut(cur) {
			res[B.Group[cur][0]] = max(max_, all-sum-weight[cur])
		}
		return sum + weight[cur]
	}
	dfs(0, -1)

	for i := 0; i < n; i++ {
		fmt.Fprintln(out, res[i])
	}
}

func yukicode1326() {
	// https://yukicoder.me/problems/no/1326
	// No.1326 ふたりのDominator
	// 给定一个无向连通图
	// 对每组顶点(x,y), 你需要选定一个不为x,y的顶点z,删除z的所有邻接边,
	//                   使得x,y不再连通,问有多少种方案
	// n,m<=5e4 q<=1e5

	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m int
	fmt.Fscan(in, &n, &m)
	graph := make([][]Edge, n)
	for i := 0; i < m; i++ {
		var u, v int
		fmt.Fscan(in, &u, &v)
		u--
		v--
		graph[u] = append(graph[u], Edge{u, v, 1, i})
		graph[v] = append(graph[v], Edge{v, u, 1, i})
	}

	B := NewBlockCutTree(graph)
	B.Build()
	tree := B.Tree
	hld := NewHeavyLightDecomposition(len(tree))
	for i := 0; i < len(tree); i++ {
		for _, v := range tree[i] {
			hld.AddDirectedEdge(i, v)
		}
	}
	hld.Build(0)

	var q int
	fmt.Fscan(in, &q)
	for i := 0; i < q; i++ {
		var x, y int
		fmt.Fscan(in, &x, &y)
		x--
		y--
		if x == y {
			fmt.Fprintln(out, 0)
			continue
		}

		id1, id2 := B.Get(x), B.Get(y)
		res := hld.Dist(id1, id2)
		if B.IsNewCut(id1) {
			res--
		}
		if B.IsNewCut(id2) {
			res--
		}
		fmt.Fprintln(out, res/2)
	}

}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

type BlockCutTree struct {
	// !BlockCutTree邻接表, 新图的顶点个数为原图割点数+原图点双数.
	// ![0, len(点双)) 对应原图`去除割点`的点双.
	// ![len(点双), len(点双)+len(割点)) 对应原图的割点.
	Tree [][]int

	// BlockCutTree的每个顶点i对应的原图的顶点编号们
	// !割点所在组只有原图割点本身,即Group[i] = []int{cut}
	Group [][]int

	idar, idcc []int
	g          [][]Edge
	bcc        *_BCC
	cutCount   int
}

type Edge = struct{ from, to, cost, index int }
type Graph = [][]Edge

func NewBlockCutTree(g Graph) *BlockCutTree {
	return &BlockCutTree{g: g, bcc: _NewBCC(g)}
}

func (bct *BlockCutTree) Build() {
	bct.bcc.Build()
	cut := bct.bcc.lowLink.Articulation
	cutSize, bccSize := len(cut), len(bct.bcc.BCC)
	n := len(bct.g)
	idar, idcc := make([]int, n), make([]int, n)
	last := make([]int, n)
	for i := range idar {
		idar[i], idcc[i] = -1, -1
		last[i] = -1
	}
	for i := 0; i < len(cut); i++ {
		idar[cut[i]] = i + bccSize
	}
	bct.Tree = make([][]int, cutSize+bccSize)
	for i := 0; i < bccSize; i++ {
		st := make([]int, 0, len(bct.bcc.BCC[i])*2)
		for _, e := range bct.bcc.BCC[i] {
			st = append(st, e[0], e[1])
		}
		for _, u := range st {
			if idar[u] == -1 {
				idcc[u] = i
			} else if last[u] != i {
				bct.add(i, idar[u])
				last[u] = i
			}
		}
	}

	bct.idar, bct.idcc = idar, idcc
	bct.cutCount = cutSize

	group := make([][]int, len(bct.Tree))
	for i := 0; i < n; i++ {
		id := bct.Get(i)
		if id >= 0 {
			group[id] = append(group[id], i)
		}
	}
	bct.Group = group
}

// `原图`的顶点对应的BlockCutTree的顶点编号.
// !注意孤立点的编号为-1(不存在于BlockCutTree中).
//  0 <= rawV < len(bct.g)
func (bct *BlockCutTree) Get(rawV int) int {
	if bct.idar[rawV] >= 0 {
		return bct.idar[rawV]
	}
	return bct.idcc[rawV]
}

// `原图`的顶点是否是割点.
//  0 <= rawV < len(bct.g)
func (bct *BlockCutTree) IsRawCut(rawV int) bool { return bct.idar[rawV] >= 0 }

// `圆方树`中的顶点是否是(原图)的割点.
//  0 <= v < len(bct.Tree)
func (bct *BlockCutTree) IsNewCut(v int) bool {
	start := len(bct.bcc.BCC)
	return start <= v && v < start+bct.cutCount
}

// `原图`的顶点是否属于某个点双.
//  0 <= rawV < len(bct.g)
func (bct *BlockCutTree) IsRawVBCC(rawV int) bool { return bct.idar[rawV] < 0 && bct.idcc[rawV] >= 0 }

// `原图`的顶点是否是孤立点.
//  0 <= rawV < len(bct.g)
func (bct *BlockCutTree) IsRawIsolate(rawV int) bool { return bct.idar[rawV] < 0 && bct.idcc[rawV] < 0 }

// 原图中的割点个数.
func (bct *BlockCutTree) CountCut() int { return bct.cutCount }

func (bct *BlockCutTree) add(i, j int) {
	if i == -1 || j == -1 {
		return
	}
	bct.Tree[i] = append(bct.Tree[i], j)
	bct.Tree[j] = append(bct.Tree[j], i)
}

type _BCC struct {
	BCC     [][][2]int // 边:(from,to)
	g       [][]Edge
	lowLink *_lowlink
	used    []bool
	tmp     []Edge
}

func _NewBCC(g [][]Edge) *_BCC {
	return &_BCC{
		g:       g,
		lowLink: _NEewLowlink(g),
	}
}

func (bcc *_BCC) Build() {
	bcc.lowLink.Build()
	bcc.used = make([]bool, len(bcc.g))
	for i := 0; i < len(bcc.used); i++ {
		if !bcc.used[i] {
			bcc.dfs(i, -1)
		}
	}
}

func (bcc *_BCC) dfs(idx, par int) {
	bcc.used[idx] = true
	beet := false
	for _, next := range bcc.g[idx] {
		if next.to == par {
			b := beet
			beet = true
			if !b {
				continue
			}
		}

		if !bcc.used[next.to] || bcc.lowLink.ord[next.to] < bcc.lowLink.ord[idx] {
			bcc.tmp = append(bcc.tmp, next)
		}

		if !bcc.used[next.to] {
			bcc.dfs(next.to, idx)
			if bcc.lowLink.low[next.to] >= bcc.lowLink.ord[idx] {
				bcc.BCC = append(bcc.BCC, [][2]int{})
				for {
					e := bcc.tmp[len(bcc.tmp)-1]
					bcc.BCC[len(bcc.BCC)-1] = append(bcc.BCC[len(bcc.BCC)-1], [2]int{e.from, e.to})
					bcc.tmp = bcc.tmp[:len(bcc.tmp)-1]
					if e.index == next.index {
						break
					}
				}
			}
		}
	}
}

type _lowlink struct {
	Articulation []int // 関節点
	g            [][]Edge
	ord, low     []int
	used         []bool
}

func _NEewLowlink(g [][]Edge) *_lowlink {
	return &_lowlink{g: g}
}

func (ll *_lowlink) Build() {
	ll.used = make([]bool, len(ll.g))
	ll.ord = make([]int, len(ll.g))
	ll.low = make([]int, len(ll.g))
	k := 0
	for i := 0; i < len(ll.g); i++ {
		if !ll.used[i] {
			k = ll.dfs(i, k, -1)
		}
	}
}

func (ll *_lowlink) dfs(idx, k, par int) int {
	ll.used[idx] = true
	ll.ord[idx] = k
	k++
	ll.low[idx] = ll.ord[idx]
	isArticulation := false
	beet := false
	cnt := 0
	for _, e := range ll.g[idx] {
		if e.to == par {
			tmp := beet
			beet = true
			if !tmp {
				continue
			}
		}
		if !ll.used[e.to] {
			cnt++
			k = ll.dfs(e.to, k, idx)
			ll.low[idx] = min(ll.low[idx], ll.low[e.to])
			if par >= 0 && ll.low[e.to] >= ll.ord[idx] {
				isArticulation = true
			}
		} else {
			ll.low[idx] = min(ll.low[idx], ll.ord[e.to])
		}
	}

	if par == -1 && cnt > 1 {
		isArticulation = true
	}
	if isArticulation {
		ll.Articulation = append(ll.Articulation, idx)
	}
	return k
}

// 有时BlockCutTree 需要配合 HLD/Tree 等
//
//
//
type HeavyLightDecomposition struct {
	Tree                          [][]int
	SubSize, Depth, Parent        []int
	dfn, dfnToNode, top, heavySon []int
	dfnId                         int
}

func (hld *HeavyLightDecomposition) Build(root int) {
	hld.build(root, -1, 0)
	hld.markTop(root, root)
}

func NewHeavyLightDecomposition(n int) *HeavyLightDecomposition {
	tree := make([][]int, n)
	dfn := make([]int, n)       // vertex => dfn
	dfnToNode := make([]int, n) // dfn => vertex
	top := make([]int, n)       // 所处轻/重链的顶点（深度最小），轻链的顶点为自身
	subSize := make([]int, n)   // 子树大小
	depth := make([]int, n)     // 深度
	parent := make([]int, n)    // 父结点
	heavySon := make([]int, n)  // 重儿子
	return &HeavyLightDecomposition{
		Tree:      tree,
		dfn:       dfn,
		dfnToNode: dfnToNode,
		top:       top,
		SubSize:   subSize,
		Depth:     depth,
		Parent:    parent,
		heavySon:  heavySon,
	}
}

// 添加无向边 u-v.
func (hld *HeavyLightDecomposition) AddEdge(u, v int) {
	hld.Tree[u] = append(hld.Tree[u], v)
	hld.Tree[v] = append(hld.Tree[v], u)
}

// 添加有向边 u->v.
func (hld *HeavyLightDecomposition) AddDirectedEdge(u, v int) {
	hld.Tree[u] = append(hld.Tree[u], v)
}

// 返回树节点 u 对应的 欧拉序区间 [down, up).
//  0 <= down < up <= n.
func (hld *HeavyLightDecomposition) Id(u int) (down, up int) {
	down, up = hld.dfn[u], hld.dfn[u]+hld.SubSize[u]
	return
}

// 返回边 u-v 对应的 欧拉序起点编号.
func (hld *HeavyLightDecomposition) Eid(u, v int) int {
	id1, _ := hld.Id(u)
	id2, _ := hld.Id(v)
	if id1 < id2 {
		return id2
	}
	return id1
}

// 处理路径上的可换操作.
//   0 <= start <= end <= n, [start,end).
func (hld *HeavyLightDecomposition) QueryPath(u, v int, vertex bool, f func(start, end int)) {
	if vertex {
		hld.forEach(u, v, f)
	} else {
		hld.forEachEdge(u, v, f)
	}
}

// 处理以 root 为根的子树上的查询.
//   0 <= start <= end <= n, [start,end).
func (hld *HeavyLightDecomposition) QuerySubTree(u int, vertex bool, f func(start, end int)) {
	if vertex {
		f(hld.dfn[u], hld.dfn[u]+hld.SubSize[u])
	} else {
		f(hld.dfn[u]+1, hld.dfn[u]+hld.SubSize[u])
	}
}

func (hld *HeavyLightDecomposition) forEach(u, v int, cb func(start, end int)) {
	for {
		if hld.dfn[u] > hld.dfn[v] {
			u, v = v, u
		}
		cb(max(hld.dfn[hld.top[v]], hld.dfn[u]), hld.dfn[v]+1)
		if hld.top[u] != hld.top[v] {
			v = hld.Parent[hld.top[v]]
		} else {
			break
		}
	}
}
func (hld *HeavyLightDecomposition) LCA(u, v int) int {
	for {
		if hld.dfn[u] > hld.dfn[v] {
			u, v = v, u
		}
		if hld.top[u] == hld.top[v] {
			return u
		}
		v = hld.Parent[hld.top[v]]
	}
}

func (hld *HeavyLightDecomposition) Dist(u, v int) int {
	return hld.Depth[u] + hld.Depth[v] - 2*hld.Depth[hld.LCA(u, v)]
}

// 寻找以 start 为 top 的重链 ,heavyPath[-1] 即为重链末端节点.
func (hld *HeavyLightDecomposition) GetHeavyPath(start int) []int {
	heavyPath := []int{start}
	cur := start
	for hld.heavySon[cur] != -1 {
		cur = hld.heavySon[cur]
		heavyPath = append(heavyPath, cur)
	}
	return heavyPath
}

func (hld *HeavyLightDecomposition) forEachEdge(u, v int, cb func(start, end int)) {
	for {
		if hld.dfn[u] > hld.dfn[v] {
			u, v = v, u
		}
		if hld.top[u] != hld.top[v] {
			cb(hld.dfn[hld.top[v]], hld.dfn[v]+1)
			v = hld.Parent[hld.top[v]]
		} else {
			if u != v {
				cb(hld.dfn[u]+1, hld.dfn[v]+1)
			}
			break
		}
	}
}

func (hld *HeavyLightDecomposition) build(cur, pre, dep int) int {
	subSize, heavySize, heavySon := 1, 0, -1
	for _, next := range hld.Tree[cur] {
		if next != pre {
			nextSize := hld.build(next, cur, dep+1)
			subSize += nextSize
			if nextSize > heavySize {
				heavySize, heavySon = nextSize, next
			}
		}
	}
	hld.Depth[cur] = dep
	hld.SubSize[cur] = subSize
	hld.heavySon[cur] = heavySon
	hld.Parent[cur] = pre
	return subSize
}

func (hld *HeavyLightDecomposition) markTop(cur, top int) {
	hld.top[cur] = top
	hld.dfn[cur] = hld.dfnId
	hld.dfnId++
	hld.dfnToNode[hld.dfn[cur]] = cur
	if hld.heavySon[cur] != -1 {
		hld.markTop(hld.heavySon[cur], top)
		for _, next := range hld.Tree[cur] {
			if next != hld.heavySon[cur] && next != hld.Parent[cur] {
				hld.markTop(next, next)
			}
		}
	}
}