题意:给出一棵 N 个节点树,上面有 K 个猴子,然后竟可能删边,但是每一只猴子必须有直接相邻的猴子与之相邻。求最少剩下几条边。
分析:一条边可以用两只猴子站,这样的一条点对,越多越好,如果是ans个,ans*2>=k,那么只需要 (k+1)/2 条边。
否则,需要 ans + (k-ans*2) 条边。
现在问题就转为求这样的点对有多少,哈哈,有漏洞的DP都AC了,哈哈~~~~。
我发现标程思路也是这样,哈哈,都是bug程序!!!
唯一的解释就是 d[u][1] >= d[u][0] 感性认识
#include <bits/stdc++.h>using namespace std;const int maxn = 100005;vector<int> g[maxn];/*------- 开挂 -------*/ namespace fastIO {#define BUF_SIZE 100000// fread -> readbool IOerror = 0;char nc() {static char buf[BUF_SIZE], *pl = buf + BUF_SIZE, *pr = buf + BUF_SIZE;if(pl == pr) {pl = buf;pr = buf + fread(buf, 1, BUF_SIZE, stdin);if(pr == pl) {IOerror = 1;return -1;}}return *pl++;}inline bool blank(char ch) {return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';}void read(int &x) {char ch;while(blank(ch = nc()));if(IOerror)return;for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');}#undef BUF_SIZE }; using namespace fastIO; /*------- 完结 -------*/int d[maxn][2]; // 0 匹配 bool vis[maxn];void dp(int u,int fa) {if(vis[u]) return;vis[u] = 1;d[u][0] = d[u][1] = 0;int sum = 0;for(int i=0; i < (int)g[u].size(); i++) {int v = g[u][i];if(v==fa) continue;dp(v,u);d[u][1] += max(d[v][0],d[v][1]);sum+=d[v][0];}for(int i=0; i < (int)g[u].size(); i++) {int v = g[u][i];if(v==fa) continue;d[u][0] = max(d[u][0],sum-d[v][0]+d[v][1]+1);}}int T; int N,K; int main() {//freopen("in.txt","r",stdin); read(T);while(T--) {read(N);read(K);for(int i=0; i <= N; i++)g[i].clear();memset(vis,0,sizeof(vis));int u;for(int i=1; i < N; i++) {read(u);g[u].push_back(i+1);g[i+1].push_back(u);}dp(1,-1);int ans = max(d[1][1],d[1][0]);if(ans*2>=K)printf("%d\n",(K+1)/2);elseprintf("%d\n",ans+K-(ans*2));}return 0; }