結果

問題 No.901 K-ary εxtrεεmε
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-02-10 17:16:47
言語 Go
(1.22.1)
結果
RE  
実行時間 -
コード長 3,786 bytes
コンパイル時間 11,555 ms
コンパイル使用メモリ 210,692 KB
実行使用メモリ 98,564 KB
最終ジャッジ日時 2023-09-21 19:37:43
合計ジャッジ時間 26,455 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 357 ms
96,372 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 4 ms
4,376 KB
testcase_03 AC 4 ms
4,380 KB
testcase_04 AC 4 ms
4,376 KB
testcase_05 AC 5 ms
4,376 KB
testcase_06 AC 5 ms
4,376 KB
testcase_07 AC 429 ms
92,428 KB
testcase_08 AC 419 ms
92,408 KB
testcase_09 AC 424 ms
92,408 KB
testcase_10 AC 423 ms
92,404 KB
testcase_11 AC 422 ms
92,416 KB
testcase_12 AC 417 ms
92,428 KB
testcase_13 AC 432 ms
92,416 KB
testcase_14 AC 434 ms
92,412 KB
testcase_15 AC 409 ms
92,388 KB
testcase_16 AC 414 ms
92,428 KB
testcase_17 AC 444 ms
96,660 KB
testcase_18 AC 447 ms
96,636 KB
testcase_19 AC 444 ms
96,648 KB
testcase_20 AC 459 ms
96,680 KB
testcase_21 AC 449 ms
96,648 KB
testcase_22 AC 448 ms
96,512 KB
testcase_23 AC 449 ms
98,536 KB
testcase_24 AC 447 ms
96,680 KB
testcase_25 AC 449 ms
98,560 KB
testcase_26 AC 493 ms
98,564 KB
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n int
	fmt.Fscan(in, &n)
	edges := make([][]int, 0, n-1)
	weight := make([]map[int]int, n)
	for i := 0; i < n; i++ {
		weight[i] = make(map[int]int)
	}
	for i := 0; i < n-1; i++ {
		var u, v, w int
		fmt.Fscan(in, &u, &v, &w)
		edges = append(edges, []int{u, v})
		weight[u][v] = w
		weight[v][u] = w
	}

	A := NewAuxiliaryTree(n, edges)
	adjList := A.RawTree
	dist := make([]int, n) // !深度(带权)
	for i := 0; i < n; i++ {
		dist[i] = -1
	}
	queue := []int{0}
	dist[0] = 0
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		for _, next := range adjList[cur] {
			if dist[next] != -1 {
				continue
			}
			dist[next] = dist[cur] + weight[cur][next]
			queue = append(queue, next)
		}
	}

	var q int
	fmt.Fscan(in, &q)
	for i := 0; i < q; i++ {
		var k int
		fmt.Fscan(in, &k)
		points := make([]int, k)
		for j := 0; j < k; j++ {
			fmt.Fscan(in, &points[j])
		}

		tree, root := A.Query(points)
		res := 0
		queue := []int{root}
		for len(queue) > 0 {
			cur := queue[0]
			queue = queue[1:]
			for _, next := range tree[cur] {
				res += dist[next] - dist[cur]
				queue = append(queue, next)
			}
		}

		fmt.Fprintln(out, res)
	}
}

type AuxiliaryTree struct {
	RawTree       [][]int // 原图邻接表(无向边)
	g0            [][]int // 虚树邻接表(有向边)
	s             []int
	fs, ls, depth []int

	lg []int
	st [][]int
}

// 给定顶点个数n和无向边集(u,v)构建.
//  O(nlogn)
func NewAuxiliaryTree(n int, edges [][]int) *AuxiliaryTree {
	g := make([][]int, n)
	for _, e := range edges {
		g[e[0]] = append(g[e[0]], e[1])
		g[e[1]] = append(g[e[1]], e[0])
	}
	res := &AuxiliaryTree{
		RawTree: g,
		g0:      make([][]int, n),
		s:       []int{},
		fs:      make([]int, n),
		ls:      make([]int, n),
		depth:   make([]int, n),
	}

	res.dfs(0, -1, 0)
	res.buildSt()
	return res
}

// 指定点集,返回虚树的(有向图邻接表,虚树的根).
//  O(klogk) 构建虚树
func (t *AuxiliaryTree) Query(points []int) ([][]int, int) {
	k := len(points)
	points = append(points[:0:0], points...)
	sort.Slice(points, func(i, j int) bool {
		return t.fs[points[i]] < t.fs[points[j]]
	})

	for i := 0; i < k-1; i++ {
		x, y := t.fs[points[i]], t.fs[points[i+1]]
		l := t.lg[y-x+1]
		w := t.st[l][x]
		if t.depth[t.st[l][y-(1<<l)+1]] < t.depth[t.st[l][x]] {
			w = t.st[l][y-(1<<l)+1]
		}
		points = append(points, w)
	}

	sort.Slice(points, func(i, j int) bool {
		return t.fs[points[i]] < t.fs[points[j]]
	})

	stk := []int{}
	pre := -1
	root := -1
	for _, v := range points {
		if pre == v {
			continue
		}
		for len(stk) > 0 && t.ls[stk[len(stk)-1]] < t.fs[v] {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			parent := stk[len(stk)-1]
			t.g0[parent] = append(t.g0[parent], v)
			if root == -1 {
				root = parent
			}
		}

		t.g0[v] = t.g0[v][:0]
		stk = append(stk, v)
		pre = v
	}

	return t.g0, root
}

func (t *AuxiliaryTree) dfs(v, p, d int) {
	t.depth[v] = d
	t.fs[v] = len(t.s)
	t.s = append(t.s, v)
	for _, w := range t.RawTree[v] {
		if w == p {
			continue
		}
		t.dfs(w, v, d+1)
		t.s = append(t.s, v)
	}
	t.ls[v] = len(t.s)
	t.s = append(t.s, v)
}

func (t *AuxiliaryTree) buildSt() {
	l := len(t.s)
	lg := make([]int, l+1)
	for i := 2; i <= l; i++ {
		lg[i] = lg[i>>1] + 1
	}
	st := make([][]int, lg[l]+1)
	for i := range st {
		st[i] = make([]int, l-(1<<i)+1)
		for j := range st[i] {
			st[i][j] = l
		}
	}

	copy(st[0], t.s)
	b := 1
	for i := 0; i < lg[l]; i++ {
		st0, st1 := st[i], st[i+1]
		for j := 0; j < l-(b<<1)+1; j++ {
			st1[j] = st0[j]
			if t.depth[st0[j+b]] < t.depth[st0[j]] {
				st1[j] = st0[j+b]
			}
		}
		b <<= 1
	}

	t.lg = lg
	t.st = st
}
0