Approach
Depth-first search
For Codeforces 835F — Roads in the Kingdom, the implementation follows one branch at a time, making it suitable for components, trees, backtracking, or dependency exploration.
- Define the state carried into one recursive or stack frame.
- Mark or choose the current state before exploring children.
- Combine child results or undo the choice when the branch finishes.
Code notes
- 112 lines of Go from the credited upstream file 835F.go.
- The implementation visibly relies on sequence storage.
- 1 loop block detected, together with recursive traversal.
Complexity
Count unique states for graph traversal; for backtracking, count the branching factor and maximum depth.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1package main2 3import (4 . "fmt"5 "io"6)7 89func cf835F(in io.Reader, out io.Writer) {10 var n, diam, maxInnerDiam int11 Fscan(in, &n)12 type nb struct{ to, wt int }13 g := make([][]nb, n)14 deg := make([]int, n)15 for range n {16 var v, w, wt int17 Fscan(in, &v, &w, &wt)18 v--19 w--20 g[v] = append(g[v], nb{w, wt})21 g[w] = append(g[w], nb{v, wt})22 deg[v]++23 deg[w]++24 }25 26 q := []int{}27 for i, d := range deg {28 if d == 1 {29 q = append(q, i)30 }31 }32 for len(q) > 0 {33 v := q[0]34 q = q[1:]35 for _, e := range g[v] {36 w := e.to37 deg[w]--38 if deg[w] == 1 {39 q = append(q, w)40 }41 }42 }43 44 cycle := []nb{}45 for start, d := range deg {46 if d > 1 {47 pre := -148 cur := start49 for {50 cycle = append(cycle, nb{cur, 0})51 for _, e := range g[cur] {52 w := e.to53 if w != pre && deg[w] > 1 {54 cycle[len(cycle)-1].wt = e.wt55 pre = cur56 cur = w57 break58 }59 }60 if cur == start {61 break62 }63 }64 break65 }66 }67 m := len(cycle)68 69 var dfs func(int, int) int70 dfs = func(v, fa int) (maxL int) {71 for _, e := range g[v] {72 w := e.to73 if w != fa && deg[w] < 2 {74 subL := dfs(w, v) + e.wt75 diam = max(diam, maxL+subL)76 maxL = max(maxL, subL)77 }78 }79 return80 }81 maxL := make([]int, m)82 for i, e := range cycle {83 diam = 084 maxL[i] = dfs(e.to, -1)85 maxInnerDiam = max(maxInnerDiam, diam)86 }87 88 suf := make([]int, m+1)89 suf2 := make([]int, m)90 s, mx := 0, maxL[m-1]91 for i := m - 2; i >= 0; i-- {92 suf[i+1] = max(suf[i+2], maxL[i+1]+s)93 s += cycle[i].wt94 suf2[i] = max(suf2[i+1], maxL[i]+s+mx)95 mx = max(mx, maxL[i]-s)96 }97 ans := suf2[0]98 99 pre, pre2, s, mx := 0, 0, 0, maxL[0]100 for i := range m - 1 {101 pre = max(pre, maxL[i]+s)102 ans = min(ans, max(pre2, suf2[i+1], pre+cycle[m-1].wt+suf[i+1]))103 s += cycle[i].wt104 pre2 = max(pre2, maxL[i+1]+s+mx)105 mx = max(mx, maxL[i+1]-s)106 }107 108 Fprint(out, max(ans, maxInnerDiam))109}110 111112