結果
問題 | No.1976 Cut then Connect |
ユーザー |
|
提出日時 | 2023-03-16 10:36:35 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 236 ms / 2,000 ms |
コード長 | 4,104 bytes |
コンパイル時間 | 10,505 ms |
コンパイル使用メモリ | 239,800 KB |
実行使用メモリ | 38,784 KB |
最終ジャッジ日時 | 2024-11-24 12:20:29 |
合計ジャッジ時間 | 14,419 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
package mainimport ("bufio""fmt""os""sort")func main() {// https://yukicoder.me/problems/no/1976// No.1976 Cut then Connect-连边后树的最小直径// 给定一棵树, 你可以做以下操作:// 从树的无向边中删除一条边, 使得图的连通分量数变为2// 对于图的每个连通分量, 选择一个点, 用无向边将这两个点连接起来// !问: 操作后的树的直径的最小值是多少?// 解:// 1. 固定每条删除的边时,求出每个连通分量的直径后可以求出新直径的最小值// !此时答案为 max(x,y,ceil(x/2)+ceil(y/2)+1) 其中x,y为连通分量的直径// 2. 对不同的边,考虑换根dp即可in := bufio.NewReader(os.Stdin)out := bufio.NewWriter(os.Stdout)defer out.Flush()var n intfmt.Fscan(in, &n)R := NewRerootingSubTree(n)edges := make([][2]int, n-1)for i := 0; i < n-1; i++ {var a, b intfmt.Fscan(in, &a, &b)a, b = a-1, b-1edges[i] = [2]int{a, b}R.AddEdge(a, b, Edge{from: a, to: b, cost: 1})}// !E: (每个点处的直径,每个点到最远点的距离)R.ReRooting(func(root int) E { return E{0, 0} },func(dp1, dp2 E) E {return E{max(max(dp1.dia, dp2.dia), dp1.dist+dp2.dist), max(dp1.dist, dp2.dist)}},func(dp E, edge Edge) E {return E{dp.dia, dp.dist + 1}},)res := nfor _, e := range edges {u, v := e[0], e[1]dia1, dia2 := R.SubTree(u, v).dia, R.SubTree(v, u).diares = min(res, max(max(dia1, dia2), (dia1+1)/2+(dia2+1)/2+1))}fmt.Fprintln(out, res)}type E = struct{ dia, dist int }type Edge = struct{ from, to, cost int }type ReRootingSubTree struct {G [][]Nodeld, rd [][]Elp, rp []inte func(root int) Eop func(dp1, dp2 E) Ecomposition func(dp E, e Edge) E}type Node struct {to, rev intdata Edge}func NewRerootingSubTree(n int) *ReRootingSubTree {res := &ReRootingSubTree{G: make([][]Node, n),ld: make([][]E, n),rd: make([][]E, n),lp: make([]int, n),rp: make([]int, n),}return res}func (rr *ReRootingSubTree) AddEdge(u, v int, e Edge) {rr.G[u] = append(rr.G[u], Node{to: v, data: e})rr.G[v] = append(rr.G[v], Node{to: u, data: e})}func (rr *ReRootingSubTree) AddDirectedEdge(u, v int, e Edge) {rr.G[u] = append(rr.G[u], Node{to: v, data: e})}func (rr *ReRootingSubTree) ReRooting(e func(root int) E,op func(dp1, dp2 E) E,compositionEdge func(dp E, e Edge) E,) []E {rr.e = err.op = oprr.composition = compositionEdgen := len(rr.G)for i := 0; i < n; i++ {sort.Slice(rr.G[i], func(j, k int) bool {return rr.G[i][j].to < rr.G[i][k].to})rr.ld[i] = make([]E, len(rr.G[i])+1)rr.rd[i] = make([]E, len(rr.G[i])+1)for j := range rr.ld[i] {rr.ld[i][j] = e(i)rr.rd[i][j] = e(i)}rr.lp[i] = 0rr.rp[i] = len(rr.G[i]) - 1}for i := 0; i < n; i++ {for j := range rr.G[i] {rr.G[i][j].rev = rr.search(rr.G[rr.G[i][j].to], i)}}res := make([]E, n)for i := 0; i < n; i++ {res[i] = rr.dfs(i, -1)}return res}// !root 作为根节点时, 子树 v 的 dp 值func (rr *ReRootingSubTree) SubTree(root, v int) E {k := rr.search(rr.G[root], v)return rr.composition(rr.dfs(v, rr.G[root][k].rev), rr.G[root][k].data)}func (rr *ReRootingSubTree) dfs(root, eid int) E {for rr.lp[root] != eid && rr.lp[root] < len(rr.G[root]) {e := rr.G[root][rr.lp[root]]rr.ld[root][rr.lp[root]+1] = rr.op(rr.ld[root][rr.lp[root]], rr.composition(rr.dfs(e.to, e.rev), e.data))rr.lp[root]++}for rr.rp[root] != eid && rr.rp[root] >= 0 {e := rr.G[root][rr.rp[root]]rr.rd[root][rr.rp[root]] = rr.op(rr.rd[root][rr.rp[root]+1], rr.composition(rr.dfs(e.to, e.rev), e.data))rr.rp[root]--}if eid < 0 {return rr.rd[root][0]}return rr.op(rr.ld[root][eid], rr.rd[root][eid+1])}func (rr *ReRootingSubTree) search(vs []Node, idx int) int {return sort.Search(len(vs), func(i int) bool { return vs[i].to >= idx })}func min(a, b int) int {if a < b {return a}return b}func max(a, b int) int {if a > b {return a}return b}