题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6178
题意:给你一棵树,有只猴子要爬到树上,每只猴子必须跟一个猴子紧密联系,即两个点要有一条边连接,现在我们希望砍掉尽可能多的边但仍使条件满足,输出最少剩下的边数。
思路:贪心的思想可以知道我们要尽可能多的连通块,所以我们希望把一棵树分成尽量多的两两相连的连通块,即最大二分匹配数,又因为最小点覆盖等于最大二分匹配数,所以我们用树形去求最小的点覆盖,然后与
进行比较,如果
那么结果为
,否则为
,多出来的我们直接再把边加上去就好了,如果是奇数还要再加
,时间复杂度
。
P.S:这题读入量太大,要用读入挂。
#pragma comment(linker, "/STACK:102400000,102400000") #include <map> #include <set> #include <stack> #include <queue> #include <cmath> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <cstring> #include <sstream> #include <cstdlib> #include <iostream> #include <algorithm> #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define Key_Value ch[ch[root][1]][0] #define DBN1(a) cerr<<#a<<"="<<(a)<<"\n" #define DBN2(a,b) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n" #define DBN3(a,b,c) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n" #define DBN4(a,b,c,d) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n" #define DBN5(a,b,c,d,e) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n" #define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n" #define clr(a,x) memset(a,x,sizeof(a)) using namespace std; typedef long long ll; const int maxn=100000+5; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); #define FI(n) FastIO::read(n) namespace FastIO{ const int SIZE=1<<16; char buf[SIZE],obuf[SIZE],str[60]; int bi=SIZE,bn=SIZE,opt; int read(char *s){ while (bn){ for (;bi<bn && buf[bi]<=' ';bi++); if (bi<bn) break; bn=fread(buf,1,SIZE,stdin); bi=0; } int sn=0; while (bn){ for (;bi<bn && buf[bi]>' '; bi++) s[sn++]=buf[bi]; if (bi<bn) break; bn=fread(buf,1,SIZE,stdin); bi=0; } s[sn]=0; return sn; } bool read(int& x){ int n=read(str),bf; if (!n)return 0; int i=0;if(str[i]=='-') bf=-1,i++;else bf=1; for (x=0;i<n;i++) x=x*10+str[i]-'0'; if (bf<0) x=-x; return 1; } }; int T,n,k,dp[maxn][2]; vector<int>G[maxn]; void dfs(int u,int f){ dp[u][0]=1;//选这个点 dp[u][1]=0;//不选这个点 for (int i=0;i<(int)G[u].size();i++){ int v=G[u][i]; if (v==f) continue; dfs(v,u); dp[u][0]+=min(dp[v][0],dp[v][1]);//选了这个点就要与下面所有的连边,还要尽可能小 dp[u][1]+=dp[v][0]; } } int main(){ for (FI(T);T--;){ FI(n),FI(k); for (int i=1;i<=n;i++) G[i].clear(); for (int i=2;i<=n;i++){ int x;FI(x); G[i].push_back(x); G[x].push_back(i); } dfs(1,-1); int ans=min(dp[1][0],dp[1][1]); if (k&1){ k--; if (k<=ans*2) printf("%d\n",k/2+1); else printf("%d\n",(k-ans*2)+ans+1); } else{ if (k<=ans*2) printf("%d\n",k/2); else printf("%d\n",(k-ans*2)+ans); } } return 0; }