LeetCode 2581.统计可能的树根数目：换根DP(树形DP)

【LetMeFly】2581.统计可能的树根数目：换根DP(树形DP)

力���题目链接：https://leetcode.cn/problems/count-number-of-possible-root-nodes/

Alice 有一棵 n 个节点的树，节点编号为 0 到 n - 1 。树用一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ai, bi] ，表示树中节点 ai 和 bi 之间有一条边。

Alice 想要 Bob 找到这棵树的根。她允许 Bob 对这棵树进行若干次 猜测 。每一次猜测，Bob 做如下事情：

• 选择两个 不相等 的整数 u 和 v ，且树中必须存在边 [u, v] 。
• Bob 猜测树中 u 是 v 的 父节点 。

  Bob 的猜测用二维整数数组 guesses 表示，其中 guesses[j] = [uj, vj] 表示 Bob 猜 uj 是 vj 的父节点。

  Alice 非常懒，她不想逐个回答 Bob 的猜测，只告诉 Bob 这些猜测里面 至少 有 k 个猜测的结果为 true 。

  给你二维整数数组 edges ，Bob 的所有猜测和整数 k ，请你返回可能成为树根的 节点数目 。如果没有这样的树，则返回 0。

   

  示例 1：

  输入：edges = [[0,1],[1,2],[1,3],[4,2]], guesses = [[1,3],[0,1],[1,0],[2,4]], k = 3输出：3解释：根为节点 0 ，正确的猜测为 [1,3], [0,1], [2,4]根为节点 1 ，正确的猜测为 [1,3], [1,0], [2,4]根为节点 2 ，正确的猜测为 [1,3], [1,0], [2,4]根为节点 3 ，正确的猜测为 [1,0], [2,4]根为节点 4 ，正确的猜测为 [1,3], [1,0]节点 0 ，1 或 2 为根时，可以得到 3 个正确的猜测。

  示例 2：

  输入：edges = [[0,1],[1,2],[2,3],[3,4]], guesses = [[1,0],[3,4],[2,1],[3,2]], k = 1输出：5解释：根为节点 0 ，正确的猜测为 [3,4]根为节点 1 ，正确的猜测为 [1,0], [3,4]根为节点 2 ，正确的猜测为 [1,0], [2,1], [3,4]根为节点 3 ，正确的猜测为 [1,0], [2,1], [3,2], [3,4]根为节点 4 ，正确的猜测为 [1,0], [2,1], [3,2]任何节点为根，都至少有 1 个正确的猜测。

   

  提示：

  • edges.length == n - 1
  • 2 private: int cnt; // 以0为根时答对的数目 int ans; int k; vector for (int nextNode : graph[thisNode]) { if (nextNode == lastNode) { continue; } if (se.count((ll)thisNode * 1000000 + nextNode)) { cnt++; } dfs(nextNode, thisNode); } } void change(int thisNode, int lastNode, int cnt) { int cnt_bak = cnt; for (int nextNode : graph[thisNode]) { if (nextNode == lastNode) { continue; } if (se.count((ll)thisNode * 1000000 + nextNode)) { cnt--; } if (se.count((ll)nextNode * 1000000 + thisNode)) { cnt++; } ans += cnt = k; change(nextNode, thisNode, cnt); cnt = cnt_bak; } }public: int rootCount(vector graph.resize(edges.size() + 1); for (vector graph[edge[0]].push_back(edge[1]); graph[edge[1]].push_back(edge[0]); } for (vector se.insert((ll)guess[0] * 1000000 + guess[1]); } cnt = 0; this-k = k; dfs(0); ans = cnt = k; change(0, -1, cnt); return ans; }};h5Python/h5 pre from typing import Listclass Solution: # AC,100.00%,92.59% def dfs(self, thisNode: int, lastNode: int) - None: for nextNode in self.graph[thisNode]: if nextNode == lastNode: continue if (thisNode * 1000000 + nextNode) in self.se: self.cnt += 1 self.dfs(nextNode, thisNode) def change(self, thisNode: int, lastNode: int, cnt: int) - None: cnt_bak = cnt for nextNode in self.graph[thisNode]: if nextNode == lastNode: continue if (thisNode * 1000000 + nextNode) in self.se: cnt -= 1 if (nextNode * 1000000 + thisNode) in self.se: cnt += 1 self.ans += cnt = self.k self.change(nextNode, thisNode, cnt) cnt = cnt_bak def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) - int: self.graph = [[] for _ in range(len(edges) + 1)] for x, y in edges: self.graph[x].append(y) self.graph[y].append(x) self.se = set() for x, y in guesses: self.se.add(x * 1000000 + y) self.cnt = 0 self.dfs(0, -1) self.k = k self.ans = 1 if self.cnt >= k else 0 self.change(0, -1, self.cnt) return self.ans

    同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

    Tisfy：https://letmefly.blog.csdn.net/article/details/136372137