結果

問題 No.1637 Easy Tree Query
コンテスト
ユーザー ID 21712
提出日時 2026-05-13 18:52:04
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 176 ms / 2,000 ms
コード長 1,157 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,228 ms
コンパイル使用メモリ 275,524 KB
実行使用メモリ 35,840 KB
最終ジャッジ日時 2026-05-13 18:52:33
合計ジャッジ時間 19,883 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "os"
import bf "bufio"

func main() {
	rd:=bf.NewReader(Stdin)
	wr:=bf.NewWriter(Stdout)
	defer wr.Flush()
	
	var n,q int
	Fscan(rd,&n,&q)
	
	tree := make([][]int, n)
	for i := 0; i < n-1; i++ {
		var a,b int
		Fscan(rd,&a,&b)
		a--
		b--
		tree[a] = append(tree[a], b)
		tree[b] = append(tree[b], a)
	}
	
	count := make([]int, n)
	
	visited := make([]bool, n)
	
	var dfs func(v int) int
	dfs = func(v int) int {
		visited[v] = true
		c := 1
		for _, n := range tree[v] {
			if !visited[n] {
				c += dfs(n)
			}
		}
		count[v] = c
		return c
	}
	
	dfs(0)
	
	sum := 0
	
	for i := 0; i < q; i++ {
		var p, x int
		Fscan(rd,&p,&x)
		p--
		sum += count[p]*x
		Fprintln(wr, sum)
	}
}

/*
考察

木を作って
各頂点ごとに部分木の頂点の個数を保持
クエリごとにその個数分に増加コストを掛け算した値を全体コストに足して表示すればいいだけ

部分木の個数数えるのが実装一番めんどい？
BFS/DFSの戻りで合算する方法のほか
葉から親へ辿るトポソ順ってやつもあるか？(入力からは親子関係不明だから面倒か)

*/
0