为什么dp数组要初始化到负无穷啊,不能初始化到0吗? 附上丑陋的代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int n,m,ans,ask;
int now;
int head[1000086];
struct node{
int next,to;
}edge[1000086];
int dp[10086][506][3];
int tmp[506][3];
int size[100086],k,udp[506][3];
int vdp[506][3];
int x,y;
void add(int x,int y){
now++;
edge[now].to=y;
edge[now].next=head[x];
head[x]=now;
}
void dfs(int pos,int fa){
/* int udp[503][6] = dp[pos];
udp[0][0]=0;
udp[1][1]=1;
udp[1][2]=1;
size[pos]=1;
for(int i=head[pos];i;i=edge[i].next){
int v = edge[i].to;
if(v == fa)continue;;
dfs(v,pos);
memset(udp,0,sizeof(udp));
udp[0][0]=0;
udp[1][1]=1;
udp[1][2]=1;
for(int s=0;s<=502;s++){
for(int j=0;j<=2;j++){
vdp[s][j]=dp[v][s][j];
}
}
for(int inu=0;inu<=min(k,size[pos])+1;inu++){
for(int inv=0;inv<=min(k,size[v])+1;inv++){
int vmax=max(vdp[inv][0],max(vdp[inv][1],vdp[inv][2]));
if(inu+inv==0||inu+inv>k+1)continue;
ndp[inu+inv][0]=max(ndp[inu+inv][0],udp[inu][0]+vmax);
ndp[inu+inv][2]=max(ndp[inu+inv][2],udp[inu][2]+vmax);
ndp[inu+inv][1]=max(ndp[inu+inv][1],udp[inu][1]+vmax);
ndp[inu+inv][1]=max(ndp[inu+inv][1],udp[inu][0]+vdp[inv][1]+1);
if(inu+inv-1>=1){
ndp[inu+inv-1][2]=std::max(ndp[inu+inv-1][2],udp[inu][1]+vdp[inv][1]);
}
}
}
size[pos]+=size[v];
}
//memcpy(udp,ndp,sizeof(ndp));
for(int i=0;i<=502;i++){
for(int j=0;j<=2;j++){
dp[pos][i][j]=ndp[i][j];
}
}*/
dp[pos][0][0]=0;
dp[pos][1][1]=1;
dp[pos][1][2]=1;
size[pos]=1;
for(int i=head[pos];i;i=edge[i].next){
int v = edge[i].to;
if(v == fa)continue;
dfs(v,pos);
memcpy(tmp,dp[pos],sizeof(dp[pos]));
for(int inu=0;inu<=min(k,size[pos])+1;inu++){
for(int inv=0;inv<=min(k,size[v])+1;inv++){
if(inu+inv==0||inu+inv>k+1)continue;
int vmax=max(dp[v][inv][0],max(dp[v][inv][1],dp[v][inv][2]));
int u=pos;
tmp[inu+inv][0]=max(tmp[inu+inv][0],dp[u][inu][0]+vmax);
tmp[inu+inv][1]=max(tmp[inu+inv][1],dp[u][inu][1]+vmax);
tmp[inu+inv][2]=max(tmp[inu+inv][2],dp[u][inu][2]+vmax);
tmp[inu+inv][1]=max(tmp[inu+inv][1],dp[u][inu][0]+dp[v][inv][1]+1);
if(inu+inv-1>=1){
tmp[inu+inv-1][2]=max(tmp[inu+inv-1][2],dp[u][inu][1]+dp[v][inv][1]);u
}
}
}
memcpy(dp[pos],tmp,sizeof(dp[pos]));
size[pos]+=size[v];
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
memset(dp,-0x3f,sizeof(dp));//0??
ans=0;
now=0;
memset(head,0,sizeof(head));
memset(size,0,sizeof(size));
scanf("%d %d",&n,&k);
for(int i=1;i<n;i++){
scanf("%d %d",&x,&y);
add(x,y);
add(y,x);
}
dfs(1,0);
for(int i=1;i<=k;i++){
ans=max(ans,max(dp[1][i][0],dp[1][i][2]));
// printf("%d %d\n",dp[1][i][0],dp[1][i][2]);
}
// for(int i=1;i<=n;i++){
// printf("%d %d %d\n",i,dp[i][1][0],dp[i][1][2]);
// }
printf("%d\n",ans);
puts("0");
}
return 0;
}