目录
一、题目
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<vector<int>>& edges, vector<vector<int>>& 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<vector<int>>& edges, vector<vector<int>>& guesses, int k) {
vector<vector<int>> 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<ll> mp;
for(auto& p : guesses) mp.insert((ll)p[0] << 32 | p[1]);
function<void(int, int)> 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<void(int, int, int)> 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;
}
};
