本文主要是介绍【CF】1695D1-Tree Queries(Easy Version) 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：1695D1
标签：动态规划
题目大意
给定一棵无根树，其中包含n个顶点。在树中隐藏了一个未知的顶点x，你需要通过查询来找出这个顶点。你可以进行k次查询，每次查询选择一个顶点v_i，在完成所有查询后，你会得到k个数字d_1, d_2, …, d_k，其中d_i表示从v_i到顶点x的最短路径上的边的数量。请注意，你知道每个距离对应哪个查询。请确定最小的k值，使得存在一些查询v_1, v_2, …, v_k，这些查询总能让你唯一地识别出顶点x，你不需要实际输出这些查询。
输入：文件的第一行包含一个整数t（1≤t≤100），表示测试用例的数量。接下来是对测试用例的描述。每个测试用例的第一行包含一个整数n（1≤n≤2000），表示树中的顶点数量。接下来的n-1行每行包含两个整数x和y（1≤x,y≤n），表示在树中有一条连接顶点x和y的边。
保证给出的边形成了一个树。保证所有测试用例的n之和不超过2000。
输出格式：对于每个测试用例，输出一个非负整数，表示所需的最少查询次数。
算法分析
- 如果n=1，则无需任何查询，因为只有一个顶点。否则，我们需要至少一次查询。如果我们固定一个节点u，并强制它成为查询，我们可以将树根固定在u上，并执行贪婪DFS以计算答案。需要注意的是，因为我们保证了根是一个查询，所以当我们为任何节点v计算答案时，我们可以假设要么是v要么是不在v子树中的某个顶点已经被查询过了。
- 我们定义ans[v]为区分v子树内所有顶点所需的最小查询次数，前提是v或不在v子树内的某个顶点已经进行了查询。注意到对于v的所有孩子c，我们需要能够区分c子树内的所有顶点，因此我们有ans[v]≥∑c ans[c]。此外，最多只能有一个孩子c的子树没有查询，否则这些孩子的所有子树都将无法通过查询区分开。如果有x>1这样的孩子，我们可以查询前x-1个孩子，这样就足以区分这些x个子树中的所有顶点。使用这个x的定义，我们的最终公式是：ans[v]=∑c ans[c]+max(0,x−1)
- 对于每个可能的根，我们递归地执行DFS来计算这些答案。答案是最小的ans[root]+1，其中+1是因为我们要对根进行查询。复杂度：O(n^2)
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int t, n;
int d[N];
vector<int> e[N];int dfs(int u, int fa){int cnt = 0, sum = 0;for (auto v : e[u]){if (v == fa) continue;int x = dfs(v, u);sum += x;if (!x) cnt ++ ;}return sum + max(0, cnt - 1);
}void solve(){cin >> n;for (int i = 1; i <= n; i ++ ){e[i].clear();d[i] = 0;}for (int i = 1; i < n; i ++ ){int u, v;cin >> u >> v;e[u].push_back(v);e[v].push_back(u);d[u] ++ , d[v] ++ ;}if (n == 1){cout << 0 << '\n';return;}int ans = 0;for (int i = 1; i <= n; i ++ ){ans = max(ans, max(1, dfs(i, 0)));}cout << ans << '\n';
}int main(){cin >> t;while (t -- ) solve();return 0;
}
这篇关于【CF】1695D1-Tree Queries(Easy Version) 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
