题意
给一个n个点的无向图，其中有一个隐藏点X,可以进行一组询问S来确定S是n个节点中的哪个点。S包括k个询问节点。询问返回的值也为k个值，每个值为X点到每个询问节点的最短路距离，求k最小为多少。
提示
1. 对于k个节点来说，最优的结构肯定是选择所有的叶子节点
2. 对于一个节点来说，假如它连了m条链（包括单个叶子节点），可以只标记m-1条链的叶子节点即可
3. 满足1，2条件以后，可以尝试再去询问点，发现均无法全部检测到，原因是：假如去点m-2条链，剩下的两条链，相同深度部分对于其他的节点来说是无法判断的，他们是等价的
方法
可以树形DP，一下，或者从每个叶子节点开始搜索一下，这里主要将树形DP的方法：
dp[i]代表除了i的子树部分外已经确定有询问点以后，子树i的内部确定所需要的询问点的最小值
只需要从度大于2的点开始DP一次就好了，因为假如度等于2的话，假如这个点连了一条直链，另一个点连了个非直链，那么必须得确保根节点选了以后才对，而两个非直链则不需要选根节点，因为显然根节点没连叶子节点，不需要选。而从度>2的点开始选，那么那么必有一个点子树内部是选了的，推出这个根节点是选了的，就满足了DP的定义（外部已经有确定的点），可以DP
代码
#includeusing namespace std;vector g[200004];int dfs(int x, int fa) { int ans = 0, cnt = 0; for (auto k: g[x]) { if (k == fa)continue; int sum = dfs(k, x); if (sum == 0)cnt++; ans += sum; } return ans + max(0, cnt - 1);}void run() { int n; cin >> n; for (int i = 1; i <= n; i++)g[i].clear(); for (int i = 1; i > x >> y; g[x].emplace_back(y); g[y].emplace_back(x); } if (n == 1) { cout << "0" << '\n'; return; } for (int i = 1; i 2) { cout << dfs(i, 0) << '\n'; return; } } cout << 1 <> t; while (t --) run(); return 0;}