题解 | #B-经商#

package main

import (
	"bufio"
	. "fmt"
	"io"
	"math"
	"os"
)

type Partner struct {
	id, a, b, pid int
}

func getRoot(arr []*Partner, id int) *Partner {
	if arr[id].pid == id {
		return arr[id]
	}
	r := getRoot(arr, arr[id].pid)
	arr[id].pid = r.id
	return r
}

// https://ac.nowcoder.com/acm/problem/14545
func NC14545(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
	var T int
	for Fscan(in, &T); T > 0; T-- {
		var N, M, C int
		Fscan(in, &N, &M, &C)
		arr := make([]*Partner, N+1)
		arr[1] = &Partner{1, 0, 0, 1}
		for i := 2; i <= N; i++ {
			var a, b int
			Fscan(in, &a, &b)
			arr[i] = &Partner{i, a, b, i}
		}
		for i := 0; i < M; i++ {
			var x, y int
			Fscan(in, &x, &y)
			xr, yr := getRoot(arr, arr[x].id), getRoot(arr, arr[y].id)
			if xr != yr {
				xr.pid = yr.id
			}
		}
		dp := make([]int, C+1)
		for i := 2; i <= N; i++ {
			if getRoot(arr, arr[1].id) == getRoot(arr, arr[i].id) {
				for j := C; j >= arr[i].a; j-- {
					dp[j] = int(math.Max(float64(dp[j]), float64(dp[j-arr[i].a]+arr[i].b)))
				}
			}
		}
		Fprintln(out, dp[C])
	}
}

func main() {
	NC14545(os.Stdin, os.Stdout)
}