func componentValue(nums []int, edges [][]int) int {
g := make([][]int, len(nums))
for _, e := range edges {
x, y := e[0], e[1]
g[x] = append(g[x], y)
g[y] = append(g[y], x)
}
var target int
var dfs func(int, int) int
dfs = func(x, fa int) int {
sum := nums[x] // 价值
for _, y := range g[x] {
if y != fa {
res := dfs(y, x)
if res < 0 {
return -1
}
sum += res
}
}
if sum > target {
return -1
}
if sum == target {
return 0
}
return sum
}
total, mx := 0, 0
for _, x := range nums {
total += x
mx = max(mx, x)
}
for i := total / mx; ; i-- {
if total%i == 0 {
target = total / i
if dfs(0, -1) == 0 {
return i - 1
}
}
}
}
func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }
class Solution {
public:
int componentValue(vector<int> &nums, vector<vector<int>> &edges) {
vector<vector<int>> g(nums.size());
for (auto &e : edges) {
int x = e[0], y = e[1];
g[x].push_back(y);
g[y].push_back(x);
}
int target;
function<int(int, int)> dfs = [&](int x, int fa) {
int sum = nums[x]; // 价值
for (int y : g[x])
if (y != fa) {
int res = dfs(y, x);
if (res < 0) return -1;
sum += res;
}
if (sum > target) return -1;
return sum < target ? sum : 0;
};
int total = accumulate(nums.begin(), nums.end(), 0);
int mx = *max_element(nums.begin(), nums.end());
for (int i = total / mx;; --i)
if (total % i == 0) {
target = total / i;
if (dfs(0, -1) == 0) return i - 1;
}
}
};
class Solution {
private List<Integer>[] g;
private int[] nums;
private int target;
public int componentValue(int[] nums, int[][] edges) {
g = new ArrayList[nums.length];
Arrays.setAll(g, e -> new ArrayList<>());
for (var e : edges) {
int x = e[0], y = e[1];
g[x].add(y);
g[y].add(x);
}
this.nums = nums;
var total = Arrays.stream(nums).sum();
var max = Arrays.stream(nums).max().orElseThrow();
for (var i = total / max; ; --i)
if (total % i == 0) {
target = total / i;
if (dfs(0, -1) == 0) return i - 1;
}
}
private int dfs(int x, int fa) {
var sum = nums[x]; // 价值
for (var y : g[x])
if (y != fa) {
var res = dfs(y, x);
if (res < 0) return -1;
sum += res;
}
if (sum > target) return -1;
return sum < target ? sum : 0;
}
}
class Solution:
def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:
g = [[] for _ in nums]
for x, y in edges:
g[x].append(y)
g[y].append(x)
def dfs(x: int, fa: int) -> int:
s = nums[x] # 价值
for y in g[x]:
if y != fa:
res = dfs(y, x)
if res < 0: return -1
s += res
if s > target: return -1
return s if s < target else 0
total = sum(nums)
for i in range(total // max(nums), 1, -1):
if total % i == 0:
target = total // i
if dfs(0, -1) == 0: return i - 1
return 0
