题面

1

9 4

4 1

1 5

1 2

3 2

3 6

6 7

6 8

9 6

0 1 0 1 0 0 1 0 1

3 2

7 3

4 0

9 5

YES

YES

NO

NO

题解

n <= 5000 可以用DP做

把答案都算出来存在一个数组f[x][y]中，表示当询问为 x 和 y 时能不能达到，查询时就可以直接访问了。

令dp[x][y][2]记录以 x 为根的子树中选 y 个点（包括 x ），最大的黑点数max以及最小的黑点数min，求出来后把 f[y][min~max] 全都赋为 1。

接下来我们要证明两个结论：

min~max中间的值都可取

考虑绿色的部分是最小值的联通子树，蓝色部分是最大值的联通子树（重合部分为渐变色）

只需要证明当我们从最小值过渡到最大值时，它是连续的就行，从最小值过渡到最大值，由于选的点数不变，一直为 y ，所以每次在绿色部分缩回一个点，蓝色部分扩张一个点，绿色部分会让累计黑点数减 1 或 0，蓝色部分会让累计黑点数加 1 或 0 ，所以每次变化会使累计数 +1，-1或不变，在整数上是连续的。

复杂度为O(n^2)

dp的转移实际上是在做树上背包，枚举儿子的时候每次是双层循环，第一层是前几个儿子子树累计的size，第二层是新的儿子子树的size，所以也就相当于在前几个儿子的所有子树中找一个点，再在新儿子子树中找一个点，然后在 lca 上也就是 x 上转移，那么宏观上来说就是每两个点计算一次，复杂度O(n^2)，f 数组处理可以差分，也是O(n^2)。

最后，为了卡空间，我把最大值和最小值存在一个int中了。

CODE

#include<map>

#include<stack>

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 5005

#define LL long long

#define DB double

#define ENDL putchar('\n')

#define lowbit(x) ((-x) & (x))

LL read() {

	LL f = 1,x = 0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f * x;

}

const int MOD1 = 1000000007;

const int sq = 10000;

int n,m,i,j,s,o,k;

vector<int> g[MAXN];

int f[MAXN][MAXN];

int dp[MAXN][MAXN];

int c[MAXN],son[MAXN];

void dfs(int x,int fa) {

	for(int i = 0;i <= n;i ++) dp[x][i] = n+1;

	dp[x][1] = c[x] * sq + c[x];

	son[x] = 1;

	for(int i = 0;i < (int)g[x].size();i ++) {

		int y = g[x][i];

		if(y != fa) {

			dfs(y,x);

			for(int k = son[x] + son[y];k > 1;k --) {

				for(int j = max(1,k-son[x]);j <= son[y] && j < k;j ++) {

					int dp0,dp1;

					dp0 = min(dp[x][k]%sq,(dp[x][k-j]%sq) + (dp[y][j]%sq));

					dp1 = max(dp[x][k]/sq,(dp[x][k-j]/sq) + (dp[y][j]/sq));

					dp[x][k] = dp1 * sq + dp0;

				}

			}

			son[x] += son[y];

		}

	}

	for(int i = 1;i <= son[x];i ++) {

		int ll = dp[x][i]%sq,rr = dp[x][i]/sq;

		if(ll <= rr) f[i][ll] ++,f[i][rr+1] --;

	}

	return ;

}

int main() {

//	freopen("tree.in","r",stdin);

//	freopen("tree.out","w",stdout);

	int T = read();

	while(T --) {

		n = read();m = read();

		memset(f,0,sizeof(f));

		memset(c,0,sizeof(c));

		memset(dp,0,sizeof(dp));

		memset(son,0,sizeof(son));

		for(int i = 1;i <= n;i ++) g[i].clear();

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

			s = read();o = read();

			g[s].push_back(o);

			g[o].push_back(s);

		}

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

			c[i] = (bool)read();

		}

		dfs(1,0);

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

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

				f[i][j] += f[i][j-1];

			}

		}

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

			s = read();o = read();

			if(s == 0 && o == 0) printf("YES\n");

			else if(s < 1 || s > n || o < 0 || o > s) printf("NO\n");

			else printf(f[s][o] > 0 ? "YES\n":"NO\n");

		}

		ENDL;

	}

	return 0;

}

巴特西

小A的树 - 树形DP

题面

题解

min~max中间的值都可取

复杂度为O(n^2)

CODE

最新文章

热门文章