當前位置：首頁 > news >正文

廣州家居網站設計nba最新交易匯總

news 2025/7/4 2:51:27

廣州家居網站設計,nba最新交易匯總,南坪網站建設哪里好,網站建設需要多少錢費用樹形DP（靈神筆記） 543 二叉樹的直徑 543. 二叉樹的直徑 - 力扣（LeetCode） 給你一棵二叉樹的根節(jié)點，返回該樹的直徑。二叉樹的直徑是指樹中任意兩個節(jié)點之間最長路徑的長度。這條路徑可能經過也可能不經過根…

樹形DP（靈神筆記）

543 二叉樹的直徑

543. 二叉樹的直徑 - 力扣（LeetCode）

給你一棵二叉樹的根節(jié)點，返回該樹的直徑。

二叉樹的直徑是指樹中任意兩個節(jié)點之間最長路徑的長度。這條路徑可能經過也可能不經過根節(jié)點 root 。

兩節(jié)點之間路徑的長度由它們之間邊數(shù)表示。

示例 1：

輸入：root = [1,2,3,4,5]
輸出：3
解釋：3 ，取路徑 [4,2,1,3] 或 [5,2,1,3] 的長度。

示例 2：

輸入：root = [1,2]
輸出：1

提示：

樹中節(jié)點數(shù)目在范圍 [1, 104] 內
-100 <= Node.val <= 100

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int ans; public int diameterOfBinaryTree(TreeNode root) {dfs(root);return ans;}private int dfs(TreeNode root) {if (root == null) {return -1;//返回-1 下面+1變成了0}int l_len = dfs(root.left) + 1;//左子樹最大鏈長+1int r_len = dfs(root.right) + 1;//右子樹最大鏈長+1ans = Math.max(ans, l_len + r_len);return Math.max(l_len, r_len);}
}

124 二叉樹的最大路徑和

124. 二叉樹中的最大路徑和 - 力扣（LeetCode）

二叉樹中的路徑被定義為一條節(jié)點序列，序列中每對相鄰節(jié)點之間都存在一條邊。同一個節(jié)點在一條路徑序列中 至多出現(xiàn)一次 。該路徑 至少包含一個 節(jié)點，且不一定經過根節(jié)點。

路徑和 是路徑中各節(jié)點值的總和。

給你一個二叉樹的根節(jié)點 root ，返回其 最大路徑和 。

示例 1：

輸入：root = [1,2,3]
輸出：6
解釋：最優(yōu)路徑是 2 -> 1 -> 3 ，路徑和為 2 + 1 + 3 = 6

示例 2：

輸入：root = [-10,9,20,null,null,15,7]
輸出：42
解釋：最優(yōu)路徑是 15 -> 20 -> 7 ，路徑和為 15 + 20 + 7 = 42

提示：

樹中節(jié)點數(shù)目范圍是 [1, 3 * 104]
-1000 <= Node.val <= 1000

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int ans = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {dfs(root);return ans;}private int dfs(TreeNode root) {if (root == null) {return 0;//沒有結點 和為0}int l_val = dfs(root.left);int r_val = dfs(root.right);ans = Math.max(ans, l_val + r_val + root.val);return Math.max(Math.max(l_val, r_val) + root.val, 0);//負數(shù)不選}
}

2246 相鄰字符不同的最長路徑

2246. 相鄰字符不同的最長路徑 - 力扣（LeetCode）

給你一棵樹（即一個連通、無向、無環(huán)圖），根節(jié)點是節(jié)點 0 ，這棵樹由編號從 0 到 n - 1 的 n 個節(jié)點組成。用下標從 0 開始、長度為 n 的數(shù)組 parent 來表示這棵樹，其中 parent[i] 是節(jié)點 i 的父節(jié)點，由于節(jié)點 0 是根節(jié)點，所以 parent[0] == -1 。

另給你一個字符串 s ，長度也是 n ，其中 s[i] 表示分配給節(jié)點 i 的字符。

請你找出路徑上任意一對相鄰節(jié)點都沒有分配到相同字符的 最長路徑 ，并返回該路徑的長度。

示例 1：

輸入：parent = [-1,0,0,1,1,2], s = "abacbe"
輸出：3
解釋：任意一對相鄰節(jié)點字符都不同的最長路徑是：0 -> 1 -> 3 。該路徑的長度是 3 ，所以返回 3 。
可以證明不存在滿足上述條件且比 3 更長的路徑。

示例 2：

輸入：parent = [-1,0,0,0], s = "aabc"
輸出：3
解釋：任意一對相鄰節(jié)點字符都不同的最長路徑是：2 -> 0 -> 3 。該路徑的長度為 3 ，所以返回 3 。

提示：

n == parent.length == s.length
1 <= n <= 105
對所有 i >= 1 ，0 <= parent[i] <= n - 1 均成立
parent[0] == -1
parent 表示一棵有效的樹
s 僅由小寫英文字母組成

class Solution {private List<Integer>[] g;//存儲父節(jié)點i的子節(jié)點private String s;private int ans;public int longestPath(int[] parent, String s) {this.s = s;int n = parent.length;g = new ArrayList[n];Arrays.setAll(g, e -> new ArrayList<>());for (int i = 1; i < n; i++) {//記錄父節(jié)點的子節(jié)點的索引g[parent[i]].add(i);}dfs(0);return ans + 1;//求點的個數(shù)，路徑長度+1}//計算最大長度private int dfs(int x) {int maxLen = 0;for (int y : g[x]) {int len = dfs(y) + 1;if (s.charAt(x) != s.charAt(y)) {ans = Math.max(ans, maxLen + len);//最長路徑maxLen = Math.max(maxLen, len);//左右子樹最大長度}}return maxLen;}
}

687 最長同值路徑

687. 最長同值路徑 - 力扣（LeetCode）

給定一個二叉樹的 root ，返回 最長的路徑的長度 ，這個路徑中的 每個節(jié)點具有相同值 。這條路徑可以經過也可以不經過根節(jié)點。

兩個節(jié)點之間的路徑長度 由它們之間的邊數(shù)表示。

示例 1:

輸入：root = [5,4,5,1,1,5]
輸出：2

示例 2:

輸入：root = [1,4,5,4,4,5]
輸出：2

提示:

樹的節(jié)點數(shù)的范圍是 [0, 104]
-1000 <= Node.val <= 1000
樹的深度將不超過 1000

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int ans;public int longestUnivaluePath(TreeNode root) {dfs(root);return ans;}private int dfs(TreeNode root) {if (root == null) {return -1;}int l_len = dfs(root.left) + 1;int r_len = dfs(root.right) + 1;if (root.left != null && root.left.val != root.val) {l_len = 0;}if (root.right != null && root.right.val != root.val) {r_len = 0;}ans = Math.max(ans, l_len + r_len);return Math.max(l_len, r_len);}
}

1617 統(tǒng)計子樹中城市之間最大距離

參考題解：1617. 統(tǒng)計子樹中城市之間最大距離 - 力扣（LeetCode）

給你 n 個城市，編號為從 1 到 n 。同時給你一個大小為 n-1 的數(shù)組 edges ，其中 edges[i] = [ui, vi] 表示城市 ui 和 vi 之間有一條雙向邊。題目保證任意城市之間只有唯一的一條路徑。換句話說，所有城市形成了一棵樹。

一棵子樹是城市的一個子集，且子集中任意城市之間可以通過子集中的其他城市和邊到達。兩個子樹被認為不一樣的條件是至少有一個城市在其中一棵子樹中存在，但在另一棵子樹中不存在。

對于 d 從 1 到 n-1 ，請你找到城市間 最大距離 恰好為 d 的所有子樹數(shù)目。

請你返回一個大小為 n-1 的數(shù)組，其中第 d 個元素（下標從 1 開始）是城市間 最大距離 恰好等于 d 的子樹數(shù)目。

請注意，兩個城市間距離定義為它們之間需要經過的邊的數(shù)目。

示例 1：

輸入：n = 4, edges = [[1,2],[2,3],[2,4]]
輸出：[3,4,0]
解釋：
子樹 {1,2}, {2,3} 和 {2,4} 最大距離都是 1 。
子樹 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 最大距離都為 2 。
不存在城市間最大距離為 3 的子樹。

示例 2：

輸入：n = 2, edges = [[1,2]]
輸出：[1]

示例 3：

輸入：n = 3, edges = [[1,2],[2,3]]
輸出：[2,1]

提示：

2 <= n <= 15
edges.length == n-1
edges[i].length == 2
1 <= ui, vi <= n
題目保證 (ui, vi) 所表示的邊互不相同。

class Solution {private List<Integer>[] g;private boolean[] inSet, vis;//inSet是選出來的樹(城市) vis記錄的是這個城市(樹)的直徑private int[] ans;private int n, diameter;//定義n和直徑public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {this.n = n;g = new ArrayList[n];Arrays.setAll(g, e -> new ArrayList<>());for (var e : edges) {int x = e[0] - 1;int y = e[1] - 1;g[x].add(y);g[y].add(x);//建樹}ans = new int[n - 1];inSet = new boolean[n];f(0);return ans;}private void f(int i) {if (i == n) {for (int v = 0; v < n; v++) {if (inSet[v]) {vis = new boolean[n];diameter = 0;dfs(v);break;}}if (diameter > 0 && Arrays.equals(vis, inSet)) {ans[diameter - 1]++;}return;}//不選城市if(i + 1);//選城市iinSet[i] = true;f(i + 1);inSet[i] = false;}//樹的直徑private int dfs(int x) {vis[x] = true;int maxLen = 0;for (int y : g[x]) {if (!vis[y] && inSet[y]) {int len = dfs(y) + 1;diameter = Math.max(diameter, maxLen + len);maxLen = Math.max(maxLen, len);}}return maxLen;}
}

2538 最大價值和與最小價值和的差值

參考題解：2538. 最大價值和與最小價值和的差值 - 力扣（LeetCode）

給你一個 n 個節(jié)點的無向無根圖，節(jié)點編號為 0 到 n - 1 。給你一個整數(shù) n 和一個長度為 n - 1 的二維整數(shù)數(shù)組 edges ，其中 edges[i] = [ai, bi] 表示樹中節(jié)點 ai 和 bi 之間有一條邊。

每個節(jié)點都有一個價值。給你一個整數(shù)數(shù)組 price ，其中 price[i] 是第 i 個節(jié)點的價值。

一條路徑的 價值和 是這條路徑上所有節(jié)點的價值之和。

你可以選擇樹中任意一個節(jié)點作為根節(jié)點 root 。選擇 root 為根的開銷是以 root 為起點的所有路徑中，價值和 最大的一條路徑與最小的一條路徑的差值。

請你返回所有節(jié)點作為根節(jié)點的選擇中，最大的開銷為多少。

示例 1：

輸入：n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]
輸出：24
解釋：上圖展示了以節(jié)點 2 為根的樹。左圖（紅色的節(jié)點）是最大價值和路徑，右圖（藍色的節(jié)點）是最小價值和路徑。
- 第一條路徑節(jié)點為 [2,1,3,4]：價值為 [7,8,6,10] ，價值和為 31 。
- 第二條路徑節(jié)點為 [2] ，價值為 [7] 。
最大路徑和與最小路徑和的差值為 24 。24 是所有方案中的最大開銷。

示例 2：

輸入：n = 3, edges = [[0,1],[1,2]], price = [1,1,1]
輸出：2
解釋：上圖展示了以節(jié)點 0 為根的樹。左圖（紅色的節(jié)點）是最大價值和路徑，右圖（藍色的節(jié)點）是最小價值和路徑。
- 第一條路徑包含節(jié)點 [0,1,2]：價值為 [1,1,1] ，價值和為 3 。
- 第二條路徑節(jié)點為 [0] ，價值為 [1] 。
最大路徑和與最小路徑和的差值為 2 。2 是所有方案中的最大開銷。

提示：

1 <= n <= 105
edges.length == n - 1
0 <= ai, bi <= n - 1
edges 表示一棵符合題面要求的樹。
price.length == n
1 <= price[i] <= 105

class Solution {private List<Integer>[] g;private int[] price;private long ans;public long maxOutput(int n, int[][] edges, int[] price) {this.price = price;g = new ArrayList[n];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);}dfs(0, -1);return ans;}private long[] dfs(int x, int father) {// maxS1前面最大帶葉子的路徑和 maxS2前面最大不帶葉子的路徑和long p = price[x], maxS1 = p, maxS2 = 0;for (var y : g[x]) {if (y != father) {var res = dfs(y, x);// s1當前不帶葉子的路徑和 s2當前帶葉子的路徑和long s1 = res[0], s2 = res[1];ans = Math.max(ans, Math.max(maxS1 + s2, maxS2 + s1));maxS1 = Math.max(maxS1, s1 + p);maxS2 = Math.max(maxS2, s2 + p);// x必然不是葉子}}return new long[]{maxS1, maxS2};}
}

337 打家劫舍三

337. 打家劫舍 III - 力扣（LeetCode）

小偷又發(fā)現(xiàn)了一個新的可行竊的地區(qū)。這個地區(qū)只有一個入口，我們稱之為 root 。

除了 root 之外，每棟房子有且只有一個“父“房子與之相連。一番偵察之后，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。如果 兩個直接相連的房子在同一天晚上被打劫 ，房屋將自動報警。

給定二叉樹的 root 。返回 在不觸動警報的情況下 ，小偷能夠盜取的最高金額。

示例 1:

輸入: root = [3,2,3,null,3,null,1]
輸出: 7 
解釋: 小偷一晚能夠盜取的最高金額 3 + 3 + 1 = 7

示例 2:

輸入: root = [3,4,5,1,3,null,1]
輸出: 9
解釋: 小偷一晚能夠盜取的最高金額 4 + 5 = 9

提示：

樹的節(jié)點數(shù)在 [1, 104] 范圍內
0 <= Node.val <= 104

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int rob(TreeNode root) {int[] ans = dfs(root);return Math.max(ans[0], ans[1]);}private int[] dfs(TreeNode root) {if (root == null) {return new int[]{0,0};}int[] left = dfs(root.left);int[] right = dfs(root.right);int rob = left[1] + right[1] + root.val;//選根節(jié)點//不選根節(jié)點int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);return new int[]{rob, notRob};}
}

1377 T秒后青蛙的位置

1377. T 秒后青蛙的位置 - 力扣（LeetCode）

參考題解：1377. T 秒后青蛙的位置 - 力扣（LeetCode）

建圖(樹)模版(以1377為例)

public static void main(String[] args) {int n = 7;int[][] edges = new int[][]{{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}};List<Integer>[] g = new ArrayList[n + 1];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); // 建樹}}

給你一棵由 n 個頂點組成的無向樹，頂點編號從 1 到 n。青蛙從 頂點 1 開始起跳。規(guī)則如下：

在一秒內，青蛙從它所在的當前頂點跳到另一個 未訪問 過的頂點（如果它們直接相連）。
青蛙無法跳回已經訪問過的頂點。
如果青蛙可以跳到多個不同頂點，那么它跳到其中任意一個頂點上的機率都相同。
如果青蛙不能跳到任何未訪問過的頂點上，那么它每次跳躍都會停留在原地。

無向樹的邊用數(shù)組 edges 描述，其中 edges[i] = [ai, bi] 意味著存在一條直接連通 ai 和 bi 兩個頂點的邊。

返回青蛙在 t 秒后位于目標頂點 target 上的概率。與實際答案相差不超過 10-5 的結果將被視為正確答案。

示例 1：

輸入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
輸出：0.16666666666666666 
解釋：上圖顯示了青蛙的跳躍路徑。青蛙從頂點 1 起跳，第 1 秒 有 1/3 的概率跳到頂點 2 ，然后第 2 秒 有 1/2 的概率跳到頂點 4，因此青蛙在 2 秒后位于頂點 4 的概率是 1/3 * 1/2 = 1/6 = 0.16666666666666666 。

示例 2：

輸入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
輸出：0.3333333333333333
解釋：上圖顯示了青蛙的跳躍路徑。青蛙從頂點 1 起跳，有 1/3 = 0.3333333333333333 的概率能夠 1 秒 后跳到頂點 7 。

提示：

1 <= n <= 100
edges.length == n - 1
edges[i].length == 2
1 <= ai, bi <= n
1 <= t <= 50
1 <= target <= n

class Solution {//自底向上查找public double frogPosition(int n, int[][] edges, int t, int target) {List<Integer>[] g = new ArrayList[n + 1];Arrays.setAll(g, e -> new ArrayList<>());g[1].add(0);// 減少額外判斷for (var e : edges) {int x = e[0], y = e[1];g[x].add(y);g[y].add(x); // 建樹}long prod = dfs(g, target, 1, 0, t);return prod != 0 ? 1.0 / prod : 0;}private long dfs(List<Integer>[] g, int target, int x, int father, int leftT) {//t秒后在targetif (leftT == 0) {return x == target ? 1 : 0;}//target是葉子停在原地if (x == target) {return g[x].size() == 1 ? 1 : 0;}for (int y : g[x]) {if (y != father) {long prod = dfs(g, target, y, x, leftT - 1);if (prod != 0) {return prod * (g[x].size() - 1);// 乘上兒子的個數(shù)}}}return 0;// 未找到 target}
}

2646 最小化旅行的價格總和

參考題解：2646. 最小化旅行的價格總和 - 力扣（LeetCode）

現(xiàn)有一棵無向、無根的樹，樹中有 n 個節(jié)點，按從 0 到 n - 1 編號。給你一個整數(shù) n 和一個長度為 n - 1 的二維整數(shù)數(shù)組 edges ，其中 edges[i] = [ai, bi] 表示樹中節(jié)點 ai 和 bi 之間存在一條邊。

每個節(jié)點都關聯(lián)一個價格。給你一個整數(shù)數(shù)組 price ，其中 price[i] 是第 i 個節(jié)點的價格。

給定路徑的 價格總和 是該路徑上所有節(jié)點的價格之和。

另給你一個二維整數(shù)數(shù)組 trips ，其中 trips[i] = [starti, endi] 表示您從節(jié)點 starti 開始第 i 次旅行，并通過任何你喜歡的路徑前往節(jié)點 endi 。

在執(zhí)行第一次旅行之前，你可以選擇一些 非相鄰節(jié)點 并將價格減半。

返回執(zhí)行所有旅行的最小價格總和。

示例 1：

輸入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
輸出：23
解釋：
上圖表示將節(jié)點 2 視為根之后的樹結構。第一個圖表示初始樹，第二個圖表示選擇節(jié)點 0 、2 和 3 并使其價格減半后的樹。
第 1 次旅行，選擇路徑 [0,1,3] 。路徑的價格總和為 1 + 2 + 3 = 6 。
第 2 次旅行，選擇路徑 [2,1] 。路徑的價格總和為 2 + 5 = 7 。
第 3 次旅行，選擇路徑 [2,1,3] 。路徑的價格總和為 5 + 2 + 3 = 10 。
所有旅行的價格總和為 6 + 7 + 10 = 23 ?？梢宰C明，23 是可以實現(xiàn)的最小答案。

示例 2：

輸入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
輸出：1
解釋：
上圖表示將節(jié)點 0 視為根之后的樹結構。第一個圖表示初始樹，第二個圖表示選擇節(jié)點 0 并使其價格減半后的樹。 
第 1 次旅行，選擇路徑 [0] 。路徑的價格總和為 1 。 
所有旅行的價格總和為 1 ?？梢宰C明，1 是可以實現(xiàn)的最小答案。

提示：

1 <= n <= 50
edges.length == n - 1
0 <= ai, bi <= n - 1
edges 表示一棵有效的樹
price.length == n
price[i] 是一個偶數(shù)
1 <= price[i] <= 1000
1 <= trips.length <= 100
0 <= starti, endi <= n - 1

class Solution {private List<Integer>[] g;private int[] price, cnt;private int end;public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {g = new ArrayList[n];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.price = price;cnt = new int[n];for (var t : trips) {end = t[1];path(t[0], -1);}int[] p = dfs(0, -1);return Math.min(p[0], p[1]);}private boolean path(int x, int father) {if (x == end) {cnt[x]++;//統(tǒng)計從start到end的路徑上的點經過了多少次return true;//找到終點}for (var y : g[x]) {if (y != father && path(y, x)) {cnt[x]++;return true;}}return false;//沒找到終點}private int[] dfs(int x, int father) {int notSelect = price[x] * cnt[x];//x不變int select = notSelect / 2;//x減半for (var y : g[x]) {if (y != father) {int[] p = dfs(y, x);//計算兒子y 不變/減半的最小價值總和notSelect += Math.min(p[0], p[1]);select += p[0];}}return new int[]{notSelect, select};}
}

2467 樹上最大得分和路徑

參考題解：2467. 樹上最大得分和路徑 - 力扣（LeetCode）

一個 n 個節(jié)點的無向樹，節(jié)點編號為 0 到 n - 1 ，樹的根結點是 0 號節(jié)點。給你一個長度為 n - 1 的二維整數(shù)數(shù)組 edges ，其中 edges[i] = [ai, bi] ，表示節(jié)點 ai 和 bi 在樹中有一條邊。

在每一個節(jié)點 i 處有一扇門。同時給你一個都是偶數(shù)的數(shù)組 amount ，其中 amount[i] 表示：

如果 amount[i] 的值是負數(shù)，那么它表示打開節(jié)點 i 處門扣除的分數(shù)。
如果 amount[i] 的值是正數(shù)，那么它表示打開節(jié)點 i 處門加上的分數(shù)。

游戲按照如下規(guī)則進行：

一開始，Alice 在節(jié)點 0 處，Bob 在節(jié)點 bob 處。
每一秒鐘，Alice 和 Bob 分別移動到相鄰的節(jié)點。Alice 朝著某個 葉子結點 移動，Bob 朝著節(jié)點 0 移動。
對于他們之間路徑上的每一個節(jié)點，Alice 和 Bob 要么打開門并扣分，要么打開門并加分。注意：
- 如果門 已經打開 （被另一個人打開），不會有額外加分也不會扣分。
- 如果 Alice 和 Bob 同時到達一個節(jié)點，他們會共享這個節(jié)點的加分或者扣分。換言之，如果打開這扇門扣 c 分，那么 Alice 和 Bob 分別扣 c / 2 分。如果這扇門的加分為 c ，那么他們分別加 c / 2 分。
如果 Alice 到達了一個葉子結點，她會停止移動。類似的，如果 Bob 到達了節(jié)點 0 ，他也會停止移動。注意這些事件互相獨立，不會影響另一方移動。

請你返回 Alice 朝最優(yōu)葉子結點移動的最大凈得分。

示例 1：

輸入：edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]
輸出：6
解釋：
上圖展示了輸入給出的一棵樹。游戲進行如下：
- Alice 一開始在節(jié)點 0 處，Bob 在節(jié)點 3 處。他們分別打開所在節(jié)點的門。Alice 得分為 -2 。
- Alice 和 Bob 都移動到節(jié)點 1 。因為他們同時到達這個節(jié)點，他們一起打開門并平分得分。Alice 的得分變?yōu)?-2 + (4 / 2) = 0 。
- Alice 移動到節(jié)點 3 。因為 Bob 已經打開了這扇門，Alice 得分不變。Bob 移動到節(jié)點 0 ，并停止移動。
- Alice 移動到節(jié)點 4 并打開這個節(jié)點的門，她得分變?yōu)?0 + 6 = 6 。
現(xiàn)在，Alice 和 Bob 都不能進行任何移動了，所以游戲結束。
Alice 無法得到更高分數(shù)。

示例 2：

輸入：edges = [[0,1]], bob = 1, amount = [-7280,2350]
輸出：-7280
解釋：
Alice 按照路徑 0->1 移動，同時 Bob 按照路徑 1->0 移動。
所以 Alice 只打開節(jié)點 0 處的門，她的得分為 -7280 。

提示：

2 <= n <= 105
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges 表示一棵有效的樹。
1 <= bob < n
amount.length == n
amount[i] 是范圍 [-104, 104] 之間的一個 偶數(shù) 。

class Solution {private int[] bobTime;private int[] amount;private int ans = Integer.MIN_VALUE;public int mostProfitablePath(int[][] edges, int bob, int[] amount) {int n = amount.length;bobTime = new int[n];Arrays.fill(bobTime, n);this.amount = amount;List<Integer>[] g = new ArrayList[n + 1];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); // 建樹}dfsBob(g, bob, -1, 0);g[0].add(-1);//防止把根節(jié)點當成葉子dfsAlice(g, 0, -1, 0, 0);return ans;}public boolean dfsBob(List<Integer>[] g, int p, int father, int time) {if (p == 0) {//到達0點bobTime[p] = time;return true;} else {boolean found0 = false;for (int e : g[p]) {if (e != father && dfsBob(g, e, p, time + 1)) {found0 = true;break;}}if (found0) {//到達0點bobTime[p] = time;}return found0;}}//total表示路徑得分public void dfsAlice(List<Integer>[] g, int p, int father, int time, int total) {if (bobTime[p] == time) {//兩人相遇total += amount[p] / 2;}if (bobTime[p] > time) {total += amount[p];}//找到葉子結點 更新答案if (g[p].size() == 1) {ans = Math.max(ans, total);return;}for (int e : g[p]) {if (e != father) {dfsAlice(g, e, p, time + 1, total);}}}
}

968 監(jiān)控二叉樹

參考：樹形 DP：監(jiān)控二叉樹【基礎算法精講 25】_嗶哩嗶哩_bilibili

給定一個二叉樹，我們在樹的節(jié)點上安裝攝像頭。

節(jié)點上的每個攝影頭都可以監(jiān)視其父對象、自身及其直接子對象。

計算監(jiān)控樹的所有節(jié)點所需的最小攝像頭數(shù)量。

示例 1：

輸入：[0,0,null,0,0]
輸出：1
解釋：如圖所示，一臺攝像頭足以監(jiān)控所有節(jié)點。

示例 2：

輸入：[0,0,null,0,null,0,null,null,0]
輸出：2
解釋：需要至少兩個攝像頭來監(jiān)視樹的所有節(jié)點。 上圖顯示了攝像頭放置的有效位置之一。

提示：

給定樹的節(jié)點數(shù)的范圍是 [1, 1000]。
每個節(jié)點的值都是 0。

思路：

藍色：安裝攝像頭
黃色：不安裝攝像頭，父節(jié)點安裝攝像頭
紅色：不安裝攝像頭，至少一個兒子安裝攝像頭

藍色=min(左藍左黃左紅)+min(右藍右黃右紅)+1

黃色=min(左藍左紅)+min(右藍右紅)

紅色=min(左藍+右紅左紅+右藍左藍+右藍)

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int minCameraCover(TreeNode root) {int[] res = dfs(root);return Math.min(res[0], res[2]);}private int[] dfs(TreeNode root) {if (root == null) {return new int[]{Integer.MAX_VALUE / 2, 0, 0};}int[] left = dfs(root.left);int[] right = dfs(root.right);int choose = Math.min(Math.min(left[0], left[1]), left[2]) + Math.min(Math.min(right[0], right[1]), right[2]) + 1;int byFather = Math.min(left[0], left[2]) + Math.min(right[0], right[2]);int byChildren = Math.min(Math.min(left[0] + right[2], left[2] + right[0]), left[0] + right[0]);return new int[]{choose, byFather, byChildren};}
}

此外，我們發(fā)現(xiàn)紅色的計算結果太多了(這一層有n個結點，總共有2^n-1種情況)，那么我們該如何優(yōu)化呢？

假設我們去掉必須選一個藍色的條件，式子變?yōu)?code>min(藍1,紅1)+min(藍2,紅2)+min(藍3,紅3)

例如，min(5,2)+min(7,6)+min(5,1)，要想選擇一個藍色，必須將一個紅色改為藍色，因此將6改為7最為合適

由此，我們知道需要找到min(藍-紅)，所以得到如下的式子：

黃色=min(藍1,紅1)+min(藍2,紅2)+min(藍3,紅3)

紅色=黃色+max(0,min(藍1-紅2 藍2-紅2 藍3-紅3))

藍色=min(藍1 黃1)+min(藍2 黃2)+min(藍3 黃3)+cost[x]

cost[x]為花費的成本

藍色一定大于紅色，所以第三個藍色的式子不用比較紅色，這就是如下的題目

保安站崗（洛谷）

SDOI2006\ 保安站崗 - 洛谷 | 計算機科學教育新生態(tài) (luogu.com.cn)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;public class Main {static int[] cost;static List<Integer>[] g;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();cost = new int[n + 1];g = new ArrayList[n + 1];//建樹Arrays.setAll(g, e -> new ArrayList<>());for (; n > 0; n--) {int v = sc.nextInt();v--;cost[v] = sc.nextInt();int m = sc.nextInt();for (; m > 0; m--) {int w = sc.nextInt();w--;g[v].add(w);g[w].add(v);}}int[] ans = dfs(0, -1);int choose = ans[0];int bySon = ans[2];System.out.println(Math.min(choose, bySon));}static int[] dfs(int x, int father) {int choose = cost[x];int byFather = 0;int minExtra = Integer.MAX_VALUE / 2;for (var y : g[x]) {if (y == father) {continue;}int[] arr = dfs(y, x);int c = arr[0];//藍色int byFa = arr[1];//黃色int bySon = arr[2];//紅色choose += Math.min(c, byFa);byFather += Math.min(c, bySon);minExtra = Math.min(minExtra, c - bySon);}return new int[]{choose, byFather, byFather + Math.max(0, minExtra)};}
}

LCP 34 二叉樹染色

LCP 34. 二叉樹染色 - 力扣（LeetCode）

小扣有一個根結點為 root 的二叉樹模型，初始所有結點均為白色，可以用藍色染料給模型結點染色，模型的每個結點有一個 val 價值。小扣出于美觀考慮，希望最后二叉樹上每個藍色相連部分的結點個數(shù)不能超過 k 個，求所有染成藍色的結點價值總和最大是多少？

示例 1：

輸入：root = [5,2,3,4], k = 2

輸出：12

解釋：結點 5、3、4 染成藍色，獲得最大的價值 5+3+4=12

示例 2：

輸入：root = [4,1,3,9,null,null,2], k = 2

輸出：16

解釋：結點 4、3、9 染成藍色，獲得最大的價值 4+3+9=16

提示：

1 <= k <= 10
1 <= val <= 10000
1 <= 結點數(shù)量 <= 10000

思路：

如果根節(jié)點是白色，那么返回左邊的最大和和右邊的最大和即f[0]=maxleft+maxright

如果根節(jié)點是藍色

當i=1時，兩個兒子都為白色此時f[i]=root.val+f[0](左)+f[0](右)；

當i=2時，一個兒子為藍色

如果k=2，可以分為左 0 右 1、左 1 右 0 此時 f[i]=max(root.val+f[0](左)+f[1](右),root.val+f[1](左)+f[0](右))
如果k=3，可分為左 0 右 2、左 1 右 1、左 2 右 0 三種情況；

最后得到 f[i]=max(val+f[j](左)+f[i-j-1](右))

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public int maxValue(TreeNode root, int k) {int[] ans = dfs(root, k);int max = Integer.MIN_VALUE;for (int a : ans) {max = Math.max(max, a);}return max;}private int[] dfs(TreeNode root, int k) {int[] f = new int[k + 1];if (root == null) {return f;}int[] left = dfs(root.left, k);int[] right = dfs(root.right, k);int maxLeft = Integer.MIN_VALUE;int maxRight = Integer.MIN_VALUE;for (int i = 0; i < k + 1; i++) {maxLeft = Math.max(maxLeft, left[i]);maxRight = Math.max(maxRight, right[i]);}f[0] = maxLeft + maxRight;for (int i = 0; i < k + 1; i++) {for (int j = 0; j < i; j++) {f[i] = Math.max(f[i], root.val + left[j] + right[i - j - 1]);}}return f;}
}

LCP 64 二叉樹燈飾

參考視頻：動態(tài)規(guī)劃樹形 DP【力扣杯2022秋·個人賽】_嗶哩嗶哩_bilibili

「力扣嘉年華」的中心廣場放置了一個巨型的二叉樹形狀的裝飾樹。每個節(jié)點上均有一盞燈和三個開關。節(jié)點值為 0 表示燈處于「關閉」狀態(tài)，節(jié)點值為 1 表示燈處于「開啟」狀態(tài)。每個節(jié)點上的三個開關各自功能如下：

開關 1：切換當前節(jié)點的燈的狀態(tài)；
開關 2：切換 以當前節(jié)點為根 的子樹中，所有節(jié)點上的燈的狀態(tài)；
開關 3：切換 當前節(jié)點及其左右子節(jié)點（若存在的話）上的燈的狀態(tài)；

給定該裝飾的初始狀態(tài) root，請返回最少需要操作多少次開關，可以關閉所有節(jié)點的燈。

示例 1：

輸入：root = [1,1,0,null,null,null,1]
輸出：2
解釋：以下是最佳的方案之一，如圖所示

示例1

示例 2：

輸入：root = [1,1,1,1,null,null,1]
輸出：1
解釋：以下是最佳的方案，如圖所示

示例2

示例 3：

輸入：root = [0,null,0]
輸出：0
解釋：無需操作開關，當前所有節(jié)點上的燈均已關閉

提示：

1 <= 節(jié)點個數(shù) <= 10^5
0 <= Node.val <= 1

思路：

任意一個結點，會受到哪些影響：

祖先結點的開關2的切換次數(shù) 偶數(shù)=不切換奇數(shù)=切換
父節(jié)點是否切換了開關3

狀態(tài)：(當前結點開關2的切換次數(shù)的奇偶性父節(jié)點是否開關3)

返回：當前狀態(tài)，最少需要操作的次數(shù)

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {private HashMap<TreeNode, int[][]> map;public int closeLampInTree(TreeNode root) {map = new HashMap<>();return dfs(root, false, false);}private int dfs(TreeNode root, boolean switch2_odd, boolean switch3) {if (root == null) return 0;//記憶化搜索int x = switch2_odd ? 1 : 0;int y = switch3 ? 1 : 0;int[][] temp = new int[2][2];if (map.containsKey(root)) {temp = map.get(root);if (temp[x][y] > 0) {return temp[x][y];}} else {map.put(root, temp);}int res = Integer.MAX_VALUE / 2;//燈打開 開關2和開關3抵消 燈開//燈關閉 開關2和開關3沒有抵消 燈開if ((root.val == 1) == (switch2_odd == switch3)) {int res1 = dfs(root.left, switch2_odd, false) + dfs(root.right, switch2_odd, false) + 1; int res2 = dfs(root.left, !switch2_odd, false) + dfs(root.right, !switch2_odd, false) + 1; int res3 = dfs(root.left, switch2_odd, true) + dfs(root.right, switch2_odd, true) + 1; int res123 = dfs(root.left, !switch2_odd, true) + dfs(root.right, !switch2_odd, true) + 3;res = Math.min(Math.min(res1, res2), Math.min(res3, res123)); } else {//燈關閉 不開開關 或者 開兩個開關int res0 = dfs(root.left, switch2_odd, false) + dfs(root.right, switch2_odd, false);int res12 = dfs(root.left, !switch2_odd, false) + dfs(root.right, !switch2_odd, false) + 2;int res13 = dfs(root.left, switch2_odd, true) + dfs(root.right, switch2_odd, true) + 2;int res23 = dfs(root.left, !switch2_odd, true) + dfs(root.right, !switch2_odd, true) + 2;res = Math.min(Math.min(res0, res12), Math.min(res13, res23));}temp[x][y] = res;return res;}
}