Linova and Kingdom
思路：我們可以很容易想到，最深的點可能是我們需要的點，我們選點都是從最深點考慮，但有種情況是，在最優的情況，我們選擇了一個點建立工廠，這個點有兩個兒子點，那這兩個兒子也一定是工廠，這兩個兒子工廠的價值會因為父親節點建立了工廠隨之減去1，這是難點，我們只需要把兩個兒子的代價轉移，保持兩個兒子點的價值，把要失去的價值給父親結點，就是父親結點的價值減去兩個兒子失去的價值2，這樣維護每個節點價值，sort一下，選擇前K個即可，
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 #include <vector> 6 7 using namespace std; 8 9 #define fi first 10 #define se second 11 #define ll long long 12 #define pb push_back 13 14 const int N = (int)2e5 + 10; 15 struct Tree{ 16 int depth; 17 int son; 18 int value; 19 void cal(){ 20 value = https://www.cnblogs.com/SSummerZzz/p/depth - son; 21 } 22 bool friend operator<(const Tree& a, const Tree& b){ 23 return a.value > b.value; 24 } 25 }tree[N]; 26 vector<int > G[N]; 27 int n, k; 28 29 void process(int now, int pre){ 30 tree[now].son = 1; 31 tree[now].depth = tree[pre].depth + 1; 32 for(int to : G[now]){ 33 if(to == pre) continue; 34 process(to, now); 35 tree[now].son += tree[to].son; 36 } 37 tree[now].cal(); 38 } 39 40 void solve(){ 41 cin >> n >> k; 42 for(int i = 1; i < n; ++i){ 43 int u, v; 44 cin >> u >> v; 45 G[u].pb(v); 46 G[v].pb(u); 47 } 48 process(1, 0); 49 sort(tree + 1, tree + 1 + n); 50 ll ans = 0; 51 for(int i = 1; i <= k; ++i){ 52 ans += tree[i].value; 53 } 54 cout << ans << endl; 55 } 56 57 int main(){ 58 59 ios::sync_with_stdio(false); 60 cin.tie(0); 61 cout.tie(0); 62 solve(); 63 64 65 return 0; 66 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/60080.html
標籤：其他
上一篇：百度PCS現在開放么?