結果
問題 | No.1098 LCAs |
ユーザー |
![]() |
提出日時 | 2021-08-17 22:09:40 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 534 ms / 2,000 ms |
コード長 | 2,228 bytes |
コンパイル時間 | 11,848 ms |
コンパイル使用メモリ | 224,664 KB |
実行使用メモリ | 83,584 KB |
最終ジャッジ日時 | 2024-10-10 22:17:43 |
合計ジャッジ時間 | 19,679 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
package mainimport ("bufio""fmt""os""strconv")var wg = bufio.NewScanner(os.Stdin)const (inf = int(1e18)initialBufSize = int(1e6)maxBufSize = int(1e6))var buf []byte = make([]byte, initialBufSize)type Graph struct {n intedges [][]int}func NewGraph(n int) *Graph {g := &Graph{n: n,edges: make([][]int, n),}for i := 0; i < n; i++ {g.edges[i] = make([]int, 0)}return g}func (g *Graph) AddEdge(u, v int) {g.edges[u] = append(g.edges[u], v)}func main() {n := nextInt()g := NewGraph(n)for i := 0; i < n-1; i++ {u, v := nextInt(), nextInt()u--v--g.AddEdge(u, v)g.AddEdge(v, u)}//visiteddist := make([]int, n)child := make([]int, n)par := make([]int, n)prev_sum := make([]int, n)dp := make([]int, n)for i := 0; i < n; i++ {par[i] = -1dist[i] = inf}S := 0dist[S] = 0var dfs func(int)dfs = func(u int) {for _, v := range g.edges[u] {if dist[v] == inf {dist[v] = dist[u] + 1par[v] = udfs(v)}}child[u]++for _, v := range g.edges[u] {if v != par[u] {child[u] += child[v]dp[u] -= prev_sum[v]}}dp[u] += child[u] * child[u]prev_sum[u] = child[u] * child[u]}dfs(S)for _, v := range dp {fmt.Printf("%d\n", v)}}// greatest common divisor (GCD) via Euclidean algorithmfunc GCD(a, b int) int {for b != 0 {t := bb = a % ba = t}return a}func modInv(a, modulo int) int {b := modulou, v := 1, 0for b > 0 {t := a / ba, b = b, a-t*bu, v = v, u-t*v}u %= moduloif u < 0 {u += modulo}return u}func powMod(x, n, mod int) int {retval := 1for mul := x; n > 0; {if n&1 == 1 {retval = retval * mul % mod}mul = mul * mul % modn >>= 1}return retval}func init() {wg.Split(bufio.ScanWords)wg.Buffer(buf, maxBufSize)}func reverse_array(array []int) []int {//reverse the slicefor i, j := 0, len(array)-1; i < j; i, j = i+1, j-1 {array[i], array[j] = array[j], array[i]}return array}func nextInt() int {wg.Scan()i, e := strconv.Atoi(wg.Text())if e != nil {panic(e)}return i}func nextStr() string {wg.Scan()i := wg.Text()return i}