leetcode 2581. 统计可能的树根数目【换根dp】

原题��接：2581. 统计可能的树根数目

题目描述：

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 =k)ans++; //更新答案 dfs2(y,x,val); } }; //然后考虑换根操作 dfs2(0,-1,cnt); return ans; }};