【JSOI2018】潜入行动

树形\(DP\)。设\(f_{i,j,0/1,0/1}\)表示以\(i\)为根的子树中，用了\(j\)个监听器，是否放置了监听器，是否被监听的方案数。转移就多讨论几种情况就好了。

关键问题是直接这么做是\(O(NK^2)\)的。

解决方案就是，我们别\(DP\)边维护子树的大小\(size\),每次枚举子树的监听器的时候不能超过\(min\{size,k\}\)。这看似只是一个常数优化，但其实可以吧复杂度降到\(O(NK)\)。

可以看这位dalao的证明

\(DP\)的时候按合并的两个子树大小分为三种情况：

两个子树\(size\)均大于\(k\)。
其中一个大于\(k\)，另一个小于等于\(k\)
两个子树大小均小于等于\(k\)

然后对于复杂度的分析：

合并一次\(O(k^2)\)，但是最多这样合并\(\frac{n}{k}\)次。
考虑小的那颗子树每个点贡献一次复杂度。并且以后不会再贡献，因为合并后子树大小大于\(k\)了。
考虑每个点贡献的次数就是每个合并时另一颗子树的大小。所以每个点最多贡献\(K\)次。

所以复杂度\(O(NK)\)

代码：

#include<bits/stdc++.h>

#define ll long long

#define N 100005

using namespace std;

inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

const ll mod=1e9+7;

int n,k;

struct road {int to,next;}s[N<<1];

int h[N],cnt;

void add(int i,int j) {s[++cnt]=(road) {j,h[i]};h[i]=cnt;}

ll f[N][105][2][2];

ll g[105][2][2];

int size[N];

void dfs(int v,int fr) {

	size[v]=1;

	f[v][0][0][0]=1;

	f[v][1][1][0]=1;

	for(int i=h[v];i;i=s[i].next) {

		int to=s[i].to;

		if(to==fr) continue ;

		dfs(to,v);

		int lim=min(k,size[v]);

		memset(g,0,sizeof(g));

		for(int j=0;j<=lim;j++) {

			int lim2=min(size[to],k-j);

			for(int q=0;q<=lim2;q++) {

				(g[j+q][0][0]+=f[v][j][0][0]*f[to][q][0][1])%=mod;

				(g[j+q][0][1]+=f[v][j][0][1]*(f[to][q][0][1]+f[to][q][1][1])+f[v][j][0][0]*f[to][q][1][1])%=mod;

				(g[j+q][1][0]+=f[v][j][1][0]*(f[to][q][0][1]+f[to][q][0][0]))%=mod;

				(g[j+q][1][1]+=f[v][j][1][1]*(f[to][q][0][0]+f[to][q][0][1]+f[to][q][1][0]+f[to][q][1][1]))%=mod;

				(g[j+q][1][1]+=f[v][j][1][0]*(f[to][q][1][0]+f[to][q][1][1]))%=mod;

			}

		}

		memcpy(f[v],g,sizeof(g));

		size[v]+=size[to];

	}

}

int main() {

	n=Get(),k=Get();

	int a,b;

	for(int i=1;i<n;i++) {

		a=Get(),b=Get();

		add(a,b),add(b,a);

	}

	dfs(1,0);

	int ans=0;

	ans=(ans+f[1][k][0][1]+f[1][k][1][1])%mod;

	cout<<ans;

	return 0;

}

巴特西

【JSOI2018】潜入行动

【JSOI2018】潜入行动

最新文章

热门文章