題目：
? 給你一棵樹，每次操作你可以刪去一條邊，最少需要多少次操作使每個節點的度數都\(<=k\)
分析：
? 我們可以想一想如何貪心，對于本題，最優的結果是讓任意一個點連的邊最多越好（但不能超過K，所以從樹的底部到根，能刪就刪，這樣可以保證，刪的邊數是最少的，
實作：
? 用dfs跑，注意的是如果沒有父節點，tot[u]的初始化為0，其余都是有一個父節點提供一條邊，對于一個節點，能刪就刪，
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cout << x << endl;
#define SZ(x) (int)x.size()
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
void read(int &x) {int s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {f = (ch == '-' ? -1 : f); ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} x = s * f;}
const int N = 100005;
int n, k;
vector<int> g[N];
int tot[N];
int res;
void init(int len)
{
rep(i, 1, len + 1)
g[i].clear(), tot[i] = 0;
res = 0;
}
void dfs(int u, int fa)
{
tot[u] = fa > 0;
for(int v : g[u])
{
if(v == fa) continue;
dfs(v, u);
tot[u] ++;
}
if(tot[u] > k)
res += tot[u] - k, tot[fa] --;
}
void solve()
{
cin >> n >> k;
init(n);
rep(i, 1, n)
{
int u, v; cin >> u >> v;
g[u].pb(v); g[v].pb(u);
}
dfs(1, -1);
cout << res << '\n';
}
signed main()
{
int _ = 1;
cin >> _;
while(_--)
solve();
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/504442.html
標籤：其他