RT,我的代码在#4 TLE了,但其他点都跑的很快,不知道为啥。有大佬愿意看一下我的代码是否有某个地方有漏洞或者说给几个比较有效的卡常方法吗QAQ,万分感谢!
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;
inline int read(){ int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; }
const int N=1e5+5,lmq=1e9+7;
struct Edge{
int to,next;
}e[N<<1];
int head[N],tot,n,k,dp[N][105][4],siz[N];
//dp[i][j][0/1/2/3]用j个监听器覆盖以i为根的子树,且i放父不放、i放父放、i不放父不放、i不放父放的方案数
void connect(int x,int y){
e[++tot]=(Edge){y,head[x]};
head[x]=tot;
}
void dfs(int now,int from){
// printf("dfs(%d,%d)\n",now,from);
int cnt=1;
siz[now]=1;
for(int i=head[now];i;i=e[i].next){
int p=e[i].to;
if(p==from) continue;
++cnt;
dfs(p,now);
}
const int M=105;
int f0[M]={1},f1[M]={1},f2[M]={1},f3[M]={1};
//f0:前i棵子树放j个 ,每棵子树的根结点放不放无所谓
//f1:前i棵子树放j个,但每棵子树的根结点都不放
//0:i放父不放 1:i不放父不放 2:i不放父放 3:i放父放
//f0[0]=f1[0]=f2[0]=f3[0]=1;
//printf("%d:\n",now);
for(int i=head[now];i;i=e[i].next){
int p=e[i].to;
if(p==from) continue;
//puts("AC");
siz[now]+=siz[p];
int lim=min(k,siz[p]);
go(j,min(k,siz[now]),0){
f0[j]=f0[j]*(dp[p][0][3]+dp[p][0][2]);
f1[j]=f1[j]*dp[p][0][1];
f2[j]=f2[j]*(dp[p][0][0]+dp[p][0][1]);
f3[j]=f3[j]*dp[p][0][2];
fo(w,1,min(j,lim)){
//f0:i放,i的父放
f0[j]=(f0[j]+f0[j-w]*(0ll+dp[p][w][3]+dp[p][w][2]))%lmq;
//f1:i不放,i的父不放,i的儿子们也全都不放
f1[j]=(f1[j]+1ll*f1[j-w]*dp[p][w][1])%lmq;
//f2:i不放,父放
f2[j]=(f2[j]+1ll*f2[j-w]*(dp[p][w][0]+dp[p][w][1]))%lmq;
//f3:i放,i的父不放,i的儿子们也全都不放
f3[j]=(f3[j]+1ll*f3[j-w]*dp[p][w][2])%lmq;
}
}
//cout<<"f3:";fo(j,0,min(k,siz[now])) printf("%d ",f3[j]);puts("");
}
//0:i放父不放 1:i不放父不放 2:i不放父放 3:i放父放
int w=min(siz[now],k);
fo(j,1,w) dp[now][j][0]=(f0[j-1]-f3[j-1]+lmq)%lmq,dp[now][j][3]=f0[j-1];
fo(j,0,w) dp[now][j][1]=(f2[j]-f1[j]+lmq)%lmq,dp[now][j][2]=f2[j];
if(siz[now]==1){
dp[now][1][0]=dp[now][0][1]=0;
dp[now][0][2]=dp[now][1][3]=1;
}else if(siz[now]==cnt){
dp[now][0][1]=dp[now][0][2]=dp[now][1][0]=0;
dp[now][1][3]=1;
}else dp[now][0][1]=dp[now][0][2]=dp[now][1][0]=dp[now][1][3]=0;
}
int main(){
cin>>n>>k;
fo(i,1,n-1){
int x=read(),y=read();
connect(x,y);
connect(y,x);
}
dfs(1,0);
cout<<(dp[1][k][0]+dp[1][k][1])%lmq;
return 0;
}
/*
-------------------------------------------------
*/