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。
输入：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 个正确的猜测。
思路：第一次dfs计算出以0为根的猜中次数cnt[0]。然后进行换根DP，换根过程中，受影响的只有两个节点的关系，考虑u是v的根，并且guess猜中了u-v，那么将u换根成v，如果v-u也被猜中了，那么换完后答案贡献不变，cnt[u] = cnt[v]，否则u-v被猜中 cnt[v] - 1，v-u被猜中 cnt[v] + 1。
时间复杂度：O(N)
空间复杂度：O(N)
class Solution {
List<Integer>[] g;
int[] cnt;
Map<Integer, HashSet<Integer>> map = new HashMap<>();
public int rootCount(int[][] edges, int[][] guesses, int k) {
int n = edges.length + 1;
g = new List[n];
cnt = new int[n];
Arrays.setAll(g, v -> new ArrayList<>());
for (int[] edge : edges) {
int x = edge[0], y = edge[1];
g[x].add(y);
g[y].add(x);
}
for (int[] guess : guesses) {
int u = guess[0], v = guess[1];
map.computeIfAbsent(v, e -> new HashSet<>()).add(u);
}
// 计算以0为根节点的猜中次数cnt[0]
dfs(0, -1);
// 换根dp计算以x为根的猜中次数cnt[x]
dfs1(0, -1);
int ans = 0;
for (int x : cnt) if (x >= k) ans++;
return ans;
}
void dfs(int x, int fa) {
for (int y : g[x]) {
if (y == fa) continue;
dfs(y, x);
}
if (fa != -1 && map.containsKey(x)) {
HashSet<Integer> set = map.get(x);
if (set.contains(fa)) cnt[0]++;
}
}
void dfs1(int x, int fa) {
if (fa != -1) {
cnt[x] = cnt[fa];
if (map.getOrDefault(x, new HashSet<>()).contains(fa)) {
cnt[x]--;
}
if (map.getOrDefault(fa, new HashSet<>()).contains(x)) {
cnt[x]++;
}
}
for (int y : g[x]) {
if (y == fa) continue;
dfs1(y, x);
}
}
}