题目大意:给n个点,每个点有一个权值,要求选k个点,这k个点任意一个点不能为其他点的父节点,求最大总权值。
思路:树形DP。ex[i]代表从开始遍历到某点x及其子节点(包括x)选i个点可以得到的最大 总权值,now[i]代表从开始遍历到某点x及其子节点(不包括x)选i个点可以得到的最大总权值,函数一开始的时候ex是代表遍历到x之前的选i个点可 以得到的最大总权值,那么在dfs算出now之后,ex[i] = max(now[i], ex[i-1] + a)就可以保证没有选的两个点是不符合要求的。
1 #include <cstdio> 2 #include <cstring> 3 4 const int MAXN = 150010; 5 6 int head[MAXN], next[MAXN], to[MAXN]; 7 int a[MAXN]; 8 int ecnt, n, k; 9 int ans[310]; 10 11 inline void addEdge(int u, int v) { 12 to[ecnt] = v; 13 next[ecnt] = head[u]; head[u] = ecnt++; 14 //printf("%d->%d ",u,v); 15 } 16 17 inline void init() { 18 memset(head, 0, sizeof(head)); 19 memset(ans, 255, sizeof(ans)); 20 ecnt = 2; 21 int f; 22 for(int i = 1; i <= n; ++i) { 23 scanf("%d%d", &f, &a[i]); 24 addEdge(f, i); 25 } 26 } 27 28 inline void _max(int &a, const int &b) { 29 if(a < b) a = b; 30 } 31 32 void dfs(int u, int *ex) { 33 int *now = new int[310]; 34 for(int i = 0; i <= k; ++i) now[i] = ex[i]; 35 for(int p = head[u]; p; p = next[p]) { 36 dfs(to[p], now); 37 } 38 ex[0] = 0; 39 for(int i = k; i > 0; --i) { 40 ex[i] = now[i]; 41 if(ex[i-1] != -1) { 42 _max(ex[i], ex[i-1] + a[u]); 43 } 44 } 45 delete [] now; 46 } 47 48 int main() { 49 while(scanf("%d%d", &n, &k) != EOF) { 50 init(); 51 dfs(0,ans); 52 if(ans[k] == -1) puts("impossible"); 53 else printf("%d ", ans[k]); 54 } 55 return 0; 56 }
By Oyking