題意
給一個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
代碼
#include<bits/stdc++.h>
using namespace std;
vector<int> 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 < n; i++) {
int x, y;
cin >> x >> y;
g[x].emplace_back(y);
g[y].emplace_back(x);
}
if (n == 1) {
cout << "0" << '\n';
return;
}
for (int i = 1; i <= n; i++) {
if (g[i].size() > 2) {
cout << dfs(i, 0) << '\n';
return;
}
}
cout << 1 << '\n';
}
int main() {
int t;
cin >> t;
while (t --)
run();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/518863.html
標籤：其他