結果

問題 No.1098 LCAs
ユーザー sgsw
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
"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 int
edges [][]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)
}
//visited
dist := 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] = -1
dist[i] = inf
}
S := 0
dist[S] = 0
var dfs func(int)
dfs = func(u int) {
for _, v := range g.edges[u] {
if dist[v] == inf {
dist[v] = dist[u] + 1
par[v] = u
dfs(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 algorithm
func GCD(a, b int) int {
for b != 0 {
t := b
b = a % b
a = t
}
return a
}
func modInv(a, modulo int) int {
b := modulo
u, v := 1, 0
for b > 0 {
t := a / b
a, b = b, a-t*b
u, v = v, u-t*v
}
u %= modulo
if u < 0 {
u += modulo
}
return u
}
func powMod(x, n, mod int) int {
retval := 1
for mul := x; n > 0; {
if n&1 == 1 {
retval = retval * mul % mod
}
mul = mul * mul % mod
n >>= 1
}
return retval
}
func init() {
wg.Split(bufio.ScanWords)
wg.Buffer(buf, maxBufSize)
}
func reverse_array(array []int) []int {
//reverse the slice
for 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
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0