我好菜啊，嘤嘤嘤
原来本地访问数组负下标不会报\(RE\)或者\(WA\)，甚至能跑出正解啊
这道题还是非常呆的
我们发现\(k\)很小，于是断定这是一个树上背包
发现在一个点上安装控制器并不能控制这个点，可能需要到父亲那边才能控制这个点，于是我们设\(dp[i][j][0/1][0/1]\)表示在以\(i\)为根的子树里放置了\(j\)个监视器，控制了除了点\(i\)以外的点，在\(i\)点装没装控制器，\(i\)点有没有被控制
大力分类套论几个转移
\(dp[i][j][0][0]\)因为没有放监视器，必须要求其儿子们在他们的子树内部就被监视了，同时因为\(i\)还没有被监视，于是儿子不能放监视器，于是从\([0][1]\)转移
\(dp[i][j][1][0]\)因为放了监视器，能监视儿子，于是儿子们有没有被监视都可以，但是都不能放监视器，于是从\([0][1]\)和\([0][0]\)转移
\(dp[i][j][0][1]\)因为没有放监视器，儿子们必须全部被监视到从\([0][1]\)转移，因为\(i\)被监视，所以至少得有一个儿子放监视器，所以至少一个从\([1][1]\)转移
\(dp[i][j][1][1]\)放了监视器，而要求被监视，从四种状态都能转移，但是要求至少有一个转移是\([1][0]\)或\([1][1]\)（放了监视器）
直接树形背包转移，之后大力容斥掉没有选择那个至少要选择的情况就好了
发现\(dp[i][j][0][1]\)要减掉的正好是\(dp[i][j][0][0]\)，\(dp[i][j][1][1]\)要减掉的正好是\(dp[i][j][1][0]\)
代码
#include#include #include #include #define re register#define LL long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))const int maxn=1e5+5;const int mod=1e9+7;inline int read() { char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}struct E{int v,nxt;}e[maxn<<1];int head[maxn],sum[maxn];int dp[maxn][105][2][2];int f[105][2][2];int n,m,num;inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}inline int qm(int a) {return a>mod?a-mod:a;}void dfs(int x,int fa) { int cur=0; sum[x]=1; for(re int i=head[x];i;i=e[i].nxt) { if(e[i].v==fa) continue; int v=e[i].v; dfs(v,x);cur++; sum[x]+=sum[v]; int U=min(sum[x],m); if(cur==1) { for(re int k=0;k<=min(sum[v],m);k++) { dp[x][k][0][0]=dp[v][k][0][1]; dp[x][k+1][1][0]=qm(dp[v][k][0][1]+dp[v][k][0][0]); dp[x][k+1][1][1]=(dp[v][k][1][1]+dp[v][k][1][0])%mod+(dp[v][k][0][0]+dp[v][k][0][1])%mod; dp[x][k+1][1][1]%=mod; dp[x][k][0][1]=qm(dp[v][k][1][1]+dp[v][k][0][1]); } continue; } for(re int j=U;j>=0;--j) { f[j][0][0]=dp[x][j][0][0],dp[x][j][0][0]=0; f[j][0][1]=dp[x][j][0][1],dp[x][j][0][1]=0; f[j][1][0]=dp[x][j][1][0],dp[x][j][1][0]=0; f[j][1][1]=dp[x][j][1][1],dp[x][j][1][1]=0; } for(re int j=U;j>=0;--j) for(re int k=0;k<=min(sum[v],m);k++) { int t=j-k; if(t<0) continue; dp[x][j][0][0]=(dp[x][j][0][0]+1ll*f[t][0][0]*dp[v][k][0][1]%mod)%mod; dp[x][j][1][0]=(dp[x][j][1][0]+1ll*f[t][1][0]*qm(dp[v][k][0][1]+dp[v][k][0][0])%mod)%mod; dp[x][j][0][1]=(dp[x][j][0][1]+1ll*f[t][0][1]*qm(dp[v][k][1][1]+dp[v][k][0][1])%mod)%mod; dp[x][j][1][1]=(dp[x][j][1][1]+1ll*f[t][1][1]*qm(qm(dp[v][k][1][1]+dp[v][k][1][0])+qm(dp[v][k][0][0]+dp[v][k][0][1]))%mod)%mod; } } if(!cur) {dp[x][0][0][0]=dp[x][1][1][0]=1;return;} for(re int j=0;j<=min(sum[x],m);j++) dp[x][j][0][1]=(dp[x][j][0][1]-dp[x][j][0][0]+mod)%mod, dp[x][j][1][1]=(dp[x][j][1][1]-dp[x][j][1][0]+mod)%mod;}int main() { n=read();m=read(); for(re int x,y,i=1;i