换根DP，LeetCode 2581. 统计可能的树根数目 目录 一、题目 1、题目描述 2、接口描述 3、原题链接 二、解题报告 1、思路分析 2、复杂度 3、代码详解 一、题目 1、题目描述 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。 2、接口描述 ​ class Solution { public: int rootCount(vector>& edges, vector>& guesses, int k) { } }; 3、原题链接 2581. 统计可能的树根数目 二、解题报告 1、思路分析 暴力思路：查询每一个节点作为根时的猜对的数目 遍历一次为O(N)，总的时间复杂度为O(N^2) 我们发现枚举完x作为根的情况再去枚举其邻接点y作为根，只会改变x，y之间的关系 也就是说，每个节点作为根的情况和其相邻节点作为根的情况具有转移关系 我们先以0为根跑一遍，统计猜测正确的数目tot 以那么0的邻接点x的猜测数目就是tot - isguessed(x, y) + isguessed(y, x) 对于猜测数对我们可以哈希表存储 其它看代码即可 2、复杂度 时间复杂度： O(n+m)空间复杂度：O(n+m) 3、代码详解 ​ class Solution { public: static constexpr int N = 1e5 + 10; typedef long long ll; int rootCount(vector>& edges, vector>& guesses, int k) { vector> g(edges.size() + 1); for(auto& p : edges) g[p[0]].emplace_back(p[1]), g[p[1]].emplace_back(p[0]); int ret = 0, tot = 0; unordered_set mp; for(auto& p : guesses) mp.insert((ll)p[0] << 32 | p[1]); function dfs = [&](int x, int fa){ for(int y : g[x]) if(y != fa) tot += mp.count((ll)x << 32 | y), dfs(y, x); }; dfs(0, -1); function foo = [&](int x, int fa, int t){ ret += t >= k; for(int y : g[x]) if(y != fa) foo(y, x, t - mp.count((ll)x << 32 | y) + mp.count((ll)y << 32 | x)); }; foo(0, -1, tot); return ret; } };