JSOI2018 潜入行动

wjh15101051's space

卧薪尝胆，厚积薄发。

JSOI2018 潜入行动

Date: Tue Apr 02 08:54:17 CST 2019

In Category: NoCategory

Description：

给一棵树，监听器可以监听他的邻居，问有多少种放置 $m$ 个监听器的方法使得所有点都被监听。

$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 100$

Solution：

状态定义不难想到： $f[i][j][0/1][0/1]$ 表示 $i$ 子树内用了 $j$ 个监听器根节点放没放，根节点被没被监听，然后转移一下就行了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 100010

#define MAXM 110

int f[MAXN][MAXM][2][2];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int siz[MAXN];

int g[MAXM][2][2];

#define MOD 1000000007

inline void Upd(int &x,int y){x = (x + y) % MOD;return;}

inline int Add(int x,int y){return (x + y >= MOD ? x + y - MOD : x + y);}

inline int Add(int a,int b,int c,int d){return Add(Add(a,b),Add(c,d));}

inline int Mul(int x,int y){return 1ll * x * y % MOD;}

int cnt = 0; 

void dp(int k,int fa)

{

	f[k][0][0][0] = f[k][1][1][0] = 1;

	siz[k] = 1;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		dp(e[i].to,k);

		register int v = e[i].to;

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

		memset(f[k],0,sizeof(f[k]));

		siz[k] += siz[e[i].to];

		for(register int j = 1;j <= min(siz[k],m);++j)

		{

			for(register int j_ = max(0,j - siz[k] + siz[v]);j_ <= min(siz[e[i].to],j);++j_)

			{

				Upd(f[k][j][0][0],Mul(g[j - j_][0][0],f[v][j_][0][1]));

				Upd(f[k][j][0][1],Add(Mul(g[j - j_][0][1],Add(f[v][j_][1][1],f[v][j_][0][1])),Mul(g[j - j_][0][0],f[v][j_][1][1])));

				Upd(f[k][j][1][0],Mul(g[j - j_][1][0],Add(f[v][j_][0][0],f[v][j_][0][1])));

				Upd(f[k][j][1][1],Add(Mul(g[j - j_][1][0],Add(f[v][j_][1][0],f[v][j_][1][1])),Mul(g[j - j_][1][1],Add(f[v][j_][0][0],f[v][j_][0][1],f[v][j_][1][0],f[v][j_][1][1]))));

			}

		}

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i < n;++i)add(rd(),rd());

	dp(1,0);

	int ans = (f[1][m][0][1] + f[1][m][1][1]) % MOD;

	cout << ans << endl;

	return 0;

}

In tag: DP-树形DP

wjh15101051