哇这道2581题超有趣的让我来给你讲讲我的解法~ 这道题就像是在玩侦探游戏我们要找出所有可能的树根嫌疑人题目大意是给我们一些从树中删除边的信息让我们推断出哪些节点可能成为原来的树根。这就像是案发现场只留下了脚印我们要还原整个故事。javaimport java.util.*;public class Solution {public int rootCount(int[][] edges, int[][] guesses, int k) {int n edges.length 1; // 节点数量// 构建邻接表表示的树ListListInteger graph new ArrayList();for (int i 0; i n; i) {graph.add(new ArrayList());}for (int[] edge : edges) {graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);}// 将guesses转换为Set方便快速查找SetString guessSet new HashSet();for (int[] guess : guesses) {guessSet.add(guess[0] , guess[1]);}// 第一次DFS以0为根计算初始猜对次数int[] correctGuesses {0};boolean[] visited new boolean[n];dfs(0, -1, graph, guessSet, correctGuesses);// 第二次DFS换根DPint[] result {0};reRootDfs(0, -1, graph, guessSet, correctGuesses[0], k, result);return result[0];}// 第一次DFS计算以0为根时猜对的次数private void dfs(int node, int parent, ListListInteger graph,SetString guessSet, int[] correctGuesses) {for (int child : graph.get(node)) {if (child parent) continue;// 检查这条边是否被正确猜测if (guessSet.contains(node , child)) {correctGuesses[0];}dfs(child, node, graph, guessSet, correctGuesses);}}// 换根DFSprivate void reRootDfs(int node, int parent, ListListInteger graph,SetString guessSet, int currentCorrect, int k, int[] result) {// 如果当前根节点满足条件if (currentCorrect k) {result[0];}for (int child : graph.get(node)) {if (child parent) continue;// 计算换根后的正确猜测数int newCorrect currentCorrect;// 移除node-child这条边的影响if (guessSet.contains(node , child)) {newCorrect--;}// 添加child-node这条边的影响if (guessSet.contains(child , node)) {newCorrect;}reRootDfs(child, node, graph, guessSet, newCorrect, k, result);}}}诶你知道吗这道题最精妙的地方在于换根DP的思想。就像是一棵树在旋转每次把一个子节点变成新的根节点我们只需要考虑边的方向变化带来的影响。我来打个比方想象你有一串圣诞灯每个灯泡都可以当作电源插头。当我们把插头从一个灯泡换到另一个时只需要关心它们之间那条线的电流方向变了没其他线路都不用重新检查这个算法的时间复杂度是O(n)超级高效有没有而且思路特别清晰先固定一个根统计答案然后通过遍历的方式转动这棵树动态维护猜对的次数。你最近是在准备面试吗这种换根DP的题目在大厂面试中还挺常见的。要是想练更多类似的题目我可以给你推荐几道经典的~要不要来个树形DP特训
