樹形DP（靈神筆記）

543 二叉樹的直徑

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

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

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

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

示例 1：

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

示例 2：

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

提示：

• 樹中節(jié)點(diǎn)數(shù)目在范圍 [1, 104] 內(nèi)
• -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é)點(diǎn)序列，序列中每對(duì)相鄰節(jié)點(diǎn)之間都存在一條邊。同一個(gè)節(jié)點(diǎn)在一條路徑序列中 至多出現(xiàn)一次 。該路徑 至少包含一個(gè) 節(jié)點(diǎn)，且不一定經(jīng)過根節(jié)點(diǎn)。

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

給你一個(gè)二叉樹的根節(jié)點(diǎn) 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é)點(diǎn)數(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;//沒有結(jié)點(diǎn) 和為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);//負(fù)數(shù)不選}
}

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

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

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

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

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

示例 1：

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

示例 2：

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

提示：

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

class Solution {private List<Integer>[] g;//存儲(chǔ)父節(jié)點(diǎn)i的子節(jié)點(diǎn)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é)點(diǎn)的子節(jié)點(diǎn)的索引g[parent[i]].add(i);}dfs(0);return ans + 1;//求點(diǎn)的個(gè)數(shù)，路徑長度+1}//計(jì)算最大長度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）

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

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

示例 1:

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

示例 2:

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

提示:

• 樹的節(jié)點(diǎn)數(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)計(jì)子樹中城市之間最大距離

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

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

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

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

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

請(qǐng)注意，兩個(gè)城市間距離定義為它們之間需要經(jīng)過的邊的數(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記錄的是這個(gè)城市(樹)的直徑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 最大價(jià)值和與最小價(jià)值和的差值

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

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

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

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

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

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

示例 1：

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

示例 2：

輸入：n = 3, edges = [[0,1],[1,2]], price = [1,1,1]
輸出：2
解釋：上圖展示了以節(jié)點(diǎn) 0 為根的樹。左圖（紅色的節(jié)點(diǎn)）是最大價(jià)值和路徑，右圖（藍(lán)色的節(jié)點(diǎn)）是最小價(jià)值和路徑。
- 第一條路徑包含節(jié)點(diǎn) [0,1,2]：價(jià)值為 [1,1,1] ，價(jià)值和為 3 。
- 第二條路徑節(jié)點(diǎn)為 [0] ，價(jià)值為 [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當(dāng)前不帶葉子的路徑和 s2當(dāng)前帶葉子的路徑和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)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口，我們稱之為 root 。

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

給定二叉樹的 root 。返回 在不觸動(dòng)警報(bào)的情況下 ，小偷能夠盜取的最高金額 。

示例 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é)點(diǎn)數(shù)在 [1, 104] 范圍內(nèi)
• 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é)點(diǎn)//不選根節(jié)點(diǎn)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 個(gè)頂點(diǎn)組成的無向樹，頂點(diǎn)編號(hào)從 1 到 n。青蛙從 頂點(diǎn) 1 開始起跳。規(guī)則如下：

• 在一秒內(nèi)，青蛙從它所在的當(dāng)前頂點(diǎn)跳到另一個(gè) 未訪問 過的頂點(diǎn)（如果它們直接相連）。
• 青蛙無法跳回已經(jīng)訪問過的頂點(diǎn)。
• 如果青蛙可以跳到多個(gè)不同頂點(diǎn)，那么它跳到其中任意一個(gè)頂點(diǎn)上的機(jī)率都相同。
• 如果青蛙不能跳到任何未訪問過的頂點(diǎn)上，那么它每次跳躍都會(huì)停留在原地。

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

返回青蛙在 t 秒后位于目標(biāo)頂點(diǎn) target 上的概率。與實(shí)際答案相差不超過 10-5 的結(jié)果將被視為正確答案。

示例 1：

輸入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
輸出：0.16666666666666666 
解釋：上圖顯示了青蛙的跳躍路徑。青蛙從頂點(diǎn) 1 起跳，第 1 秒 有 1/3 的概率跳到頂點(diǎn) 2 ，然后第 2 秒 有 1/2 的概率跳到頂點(diǎn) 4，因此青蛙在 2 秒后位于頂點(diǎn) 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
解釋：上圖顯示了青蛙的跳躍路徑。青蛙從頂點(diǎn) 1 起跳，有 1/3 = 0.3333333333333333 的概率能夠 1 秒 后跳到頂點(diǎn) 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);// 乘上兒子的個(gè)數(shù)}}}return 0;// 未找到 target}
}

2646 最小化旅行的價(jià)格總和

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

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

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

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

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

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 50
• edges.length == n - 1
• 0 <= ai, bi <= n - 1
• edges 表示一棵有效的樹
• price.length == n
• price[i] 是一個(gè)偶數(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)計(jì)從start到end的路徑上的點(diǎn)經(jīng)過了多少次return true;//找到終點(diǎn)}for (var y : g[x]) {if (y != father && path(y, x)) {cnt[x]++;return true;}}return false;//沒找到終點(diǎn)}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);//計(jì)算兒子y 不變/減半的最小價(jià)值總和notSelect += Math.min(p[0], p[1]);select += p[0];}}return new int[]{notSelect, select};}
}

2467 樹上最大得分和路徑

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

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

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

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

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

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

請(qǐng)你返回 Alice 朝最優(yōu)葉子結(jié)點(diǎn)移動(dòng)的 最大 凈得分。

示例 1：

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

示例 2：

輸入：edges = [[0,1]], bob = 1, amount = [-7280,2350]
輸出：-7280
解釋：
Alice 按照路徑 0->1 移動(dòng)，同時(shí) Bob 按照路徑 1->0 移動(dòng)。
所以 Alice 只打開節(jié)點(diǎn) 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] 之間的一個(gè) 偶數(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é)點(diǎn)當(dāng)成葉子dfsAlice(g, 0, -1, 0, 0);return ans;}public boolean dfsBob(List<Integer>[] g, int p, int father, int time) {if (p == 0) {//到達(dá)0點(diǎn)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) {//到達(dá)0點(diǎn)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];}//找到葉子結(jié)點(diǎn) 更新答案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)控二叉樹【基礎(chǔ)算法精講 25】_嗶哩嗶哩_bilibili

給定一個(gè)二叉樹，我們?cè)跇涞墓?jié)點(diǎn)上安裝攝像頭。

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

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

示例 1：

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

示例 2：

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

提示：

1. 給定樹的節(jié)點(diǎn)數(shù)的范圍是 [1, 1000]。
2. 每個(gè)節(jié)點(diǎn)的值都是 0。

思路：

• 藍(lán)色：安裝攝像頭
• 黃色：不安裝攝像頭，父節(jié)點(diǎn)安裝攝像頭
• 紅色：不安裝攝像頭，至少一個(gè)兒子安裝攝像頭

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

黃色=min(左藍(lán) 左紅)+min(右藍(lán) 右紅)

紅色=min(左藍(lán)+右紅 左紅+右藍(lán) 左藍(lán)+右藍(lán))

/*** 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)紅色的計(jì)算結(jié)果太多了(這一層有n個(gè)結(jié)點(diǎn)，總共有2^n-1種情況)，那么我們?cè)撊绾蝺?yōu)化呢？

假設(shè)我們?nèi)サ舯仨氝x一個(gè)藍(lán)色的條件，式子變?yōu)?code>min(藍(lán)1,紅1)+min(藍(lán)2,紅2)+min(藍(lán)3,紅3)

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

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

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

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

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

cost[x]為花費(fèi)的成本

藍(lán)色一定大于紅色，所以第三個(gè)藍(lán)色的式子不用比較紅色，這就是如下的題目

保安站崗（洛谷）

SDOI2006\ 保安站崗 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(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];//藍(lán)色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）

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

示例 1：

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

輸出：12

解釋：結(jié)點(diǎn) 5、3、4 染成藍(lán)色，獲得最大的價(jià)值 5+3+4=12

示例 2：

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

輸出：16

解釋：結(jié)點(diǎn) 4、3、9 染成藍(lán)色，獲得最大的價(jià)值 4+3+9=16

提示：

• 1 <= k <= 10
• 1 <= val <= 10000
• 1 <= 結(jié)點(diǎn)數(shù)量 <= 10000

思路：

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

如果根節(jié)點(diǎn)是藍(lán)色

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

當(dāng)i=2時(shí)，一個(gè)兒子為藍(lán)色

• 如果k=2，可以分為 左 0 右 1、左 1 右 0 此時(shí) 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 二叉樹燈飾

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= 節(jié)點(diǎn)個(gè)數(shù) <= 10^5
• 0 <= Node.val <= 1

思路：

任意一個(gè)結(jié)點(diǎn)，會(huì)受到哪些影響：

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

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

返回：當(dāng)前狀態(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;//燈打開 開關(guān)2和開關(guān)3抵消 燈開//燈關(guān)閉 開關(guān)2和開關(guān)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 {//燈關(guān)閉 不開開關(guān) 或者 開兩個(gè)開關(guān)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;}
}