You are given an undirected tree with tree_nodes nodes, numbered from 0 to tree_nodes - 1, and rooted at node 0. Each node initially has a binary value (0 or 1) given by the array initial[], and an expected binary value given by the array expected[].
You can perform the following operation any number of times:
Pick a node u and flip its value along with all nodes v in the subtree of u where v % 2 == u % 2. Flipping a value means toggling between 0 and 1.
Find the minimum number of operations needed so that the final binary values match expected[].
Example 1
Input:
tree_nodes = 4
tree_from = [0, 0, 1]
tree_to = [1, 2, 3]
initial = [1, 1, 0, 1]
expected = [0, 1, 1, 0]Output:
2Explanation: Pick node 0 and flip it → initial = [0, 1, 1, 1] Pick node 3 and flip it → initial = [0, 1, 1, 0] (matches expected)
Example 2
Input:
tree_nodes = 5
tree_from = [0, 1, 0, 1]
tree_to = [1, 2, 3, 4]
initial = [1, 0, 1, 1, 0]
expected = [1, 1, 0, 1, 1]Output:
3Explanation: :O
解法
DFS 自顶向下，按节点编号奇偶性分别累计已经施加的翻转次数 flipsEven 和 flipsOdd。当前节点真实值 = initial[v] XOR (v 偶数对应的累计 flips 奇偶)。若不等于期望值，则需要在此节点触发一次操作：把对应奇偶性的 flips 加 1，操作数 +1。复杂度 O(n)，空间 O(n)。
from typing import List
import sys
def min_flips_in_tree(tree_nodes: int, tree_from: List[int], tree_to: List[int],
initial: List[int], expected: List[int]) -> int:
sys.setrecursionlimit(200000)
g = [[] for _ in range(tree_nodes)]
for u, v in zip(tree_from, tree_to):
g[u].append(v); g[v].append(u)
ans = 0
seen = [False] * tree_nodes
def dfs(u, parent, flips_even, flips_odd):
nonlocal ans
my_flips = flips_even if u % 2 == 0 else flips_odd
cur = initial[u] ^ (my_flips & 1)
if cur != expected[u]:
ans += 1
if u % 2 == 0:
flips_even += 1
else:
flips_odd += 1
for nxt in g[u]:
if nxt != parent:
dfs(nxt, u, flips_even, flips_odd)
dfs(0, -1, 0, 0)
return ansimport java.util.*;
class Solution {
int ans = 0;
List<List<Integer>> g;
int minFlipsInTree(int treeNodes, int[] treeFrom, int[] treeTo, int[] initial, int[] expected) {
g = new ArrayList<>();
for (int i = 0; i < treeNodes; i++) g.add(new ArrayList<>());
for (int i = 0; i < treeFrom.length; i++) {
g.get(treeFrom[i]).add(treeTo[i]);
g.get(treeTo[i]).add(treeFrom[i]);
}
dfs(0, -1, 0, 0, initial, expected);
return ans;
}
private void dfs(int u, int parent, int flipsEven, int flipsOdd, int[] initial, int[] expected) {
int myFlips = (u % 2 == 0) ? flipsEven : flipsOdd;
int cur = initial[u] ^ (myFlips & 1);
if (cur != expected[u]) {
ans++;
if (u % 2 == 0) flipsEven++;
else flipsOdd++;
}
for (int v : g.get(u)) if (v != parent) dfs(v, u, flipsEven, flipsOdd, initial, expected);
}
}class Solution {
public:
int ans = 0;
vector<vector<int>> g;
int minFlipsInTree(int treeNodes, vector<int>& treeFrom, vector<int>& treeTo,
vector<int>& initial, vector<int>& expected) {
g.assign(treeNodes, {});
for (size_t i = 0; i < treeFrom.size(); ++i) {
g[treeFrom[i]].push_back(treeTo[i]);
g[treeTo[i]].push_back(treeFrom[i]);
}
dfs(0, -1, 0, 0, initial, expected);
return ans;
}
private:
void dfs(int u, int parent, int flipsEven, int flipsOdd,
vector<int>& initial, vector<int>& expected) {
int myFlips = (u % 2 == 0) ? flipsEven : flipsOdd;
int cur = initial[u] ^ (myFlips & 1);
if (cur != expected[u]) {
++ans;
if (u % 2 == 0) ++flipsEven; else ++flipsOdd;
}
for (int v : g[u]) if (v != parent) dfs(v, u, flipsEven, flipsOdd, initial, expected);
}
};You are given a list of products, where each product has a name, price, and weight. Your task is to determine how many duplicate products are in the list. A duplicate product is defined as a product that has the same name, price, and weight as another product in the list.
Function Parameters:
name: A list of strings where name[i] represents the name of the product at index i.
price: A list of integers where price[i] represents the price of the product at index i.
weight: A list of integers where weight[i] represents the weight of the product at index i.
Returns:
An integer denoting the number of duplicate products in the list.
Constraints
- 1 ≤ n ≤ 10⁵
- 1 ≤ price[i], weight[i] ≤ 1000
- name[i] consists of lowercase English letters (a-z) and has at most 10 characters.
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理