CodeChef - CHEFPRAD Chef and Pairs 树形DP

题意

　　　　给你一棵由 N 个节点构成的树 T。节点按照 1 到 N 编号，每个节点要么是白色，要么是黑色。有 Q 组询问，每组询问形如 (s, b)。你需要检查是否存在一个连通子图，其大小恰好是 s，并且包含恰好 b 个黑色节点。

数据

输入第一行，包含一个整数 T，表示测试数据组数。对于每组测试数据：

第一行包含两个整数 N 和 Q，分别表示树的节点个数和询问个数。

接下来 N - 1 行，每行包含两个整数 ui 和 vi，表示在树中 ui 和 vi 之间存在一条边。

接下来一行包含 N 个整数，c1, c2, ... , cN。如果 ci 为 0 表示第 i 个节点是白色的，如果 ci 为

1 表示第 i 个节点是黑色的。

接下来 Q 行，每行包含两个整数 si 和 bi，表示一组形如 (si, bi) 的询问。

对于每组询问输出一行字符串表示答案，其中 Yes 表示存在一个符合要求的连

通子图，No 表示不存在。

1 <= T <= 5, 2 <= N <= 5e3, 1 <= Q <= 1e5, 1 <= ui, vi <= N。

0 <= ci <= 1, 0 <= bi <= N, 1 <= si <= N, bi <= si。

输入

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

说明

对于第一组询问，包含由 {6, 7, 9} 构成的连通子图，其中恰包含两个黑色节点 7 和 9。

对于第二组询问，包含由 {1, 2, 3, 4, 6, 7, 8} 构成的连通子图，其中恰包含三个黑色节点 2，4和 7。

对于第三组询问和第四组询问，均不存在符合要求的连通子图。

题解：

　　观察到一个现象，对于一个子树，在子树中子图的点数确定的情况下，可行的黑点数是一个连续的区间。
　　那么很自然地用f[i][j]记下在子树i中用了j个点的情况下最多和最少的黑点数，背包一下就可以了。
　　剩下一个问题，就是复杂度。你会发现每个点对在dp的过程中都只出现一次，所以复杂度是n^2的。

#include<bits/stdc++.h>

using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18+1LL;

const double Pi = acos(-1.0);

const int N = 5e3+, M = 1e3+, mod = 1e9+,inf = 2e9;

int f[N][N][],mi[N],mx[N],c[N],siz[N];

int head[N*],t = ;

struct ss{

    int next,to;

}e[N * ];

int T,Q,n;

inline void add(int u,int v) {

    e[t].to = v;

    e[t].next = head[u];

    head[u] = t++;

}

void dfs(int u,int fa) {

    siz[u] = ;

    if(c[u])f[u][][] = f[u][][] = ;

    else f[u][][] = f[u][][] = ;

    for(int i = head[u]; i; i = e[i].next){

        int to = e[i].to;

        if(to == fa) continue;

        dfs(to,u);

        for(int k = siz[u]; k >= ; --k){

          for(int j = ; j <= siz[to]; ++j)   {

                f[u][k+j][] = min(f[u][k+j][],f[u][k][] + f[to][j][]);

                f[u][k+j][] = max(f[u][k+j][],f[u][k][] + f[to][j][]);

            }

        }

        siz[u] += siz[to];

    }

    for(int j = ; j <= siz[u]; ++j)

        mi[j] = min(mi[j],f[u][j][]),mx[j] = max(mx[j],f[u][j][]);

}

int main() {

    scanf("%d",&T);

    while(T--) {

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

        memset(head,,sizeof(head));

        t = ;

        for(int i = ; i <= n; ++i) mi[i] = inf,mx[i] = ;

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

            for(int j = ; j <= n; ++j) f[i][j][] = inf,f[i][j][] = ;

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

            int x,y;

            scanf("%d%d",&x,&y);

            add(x,y);

            add(y,x);

        }

        for(int i = ; i <= n; ++i) scanf("%d",&c[i]);

        dfs(,);

        while(Q--) {

            int x,y;

            scanf("%d%d",&x,&y);

            if(mi[x] <= y && mx[x] >= y) {

               printf("Yes\n");

            }

            else printf("No\n");

        }

    }

    return ;

}

巴特西

CodeChef - CHEFPRAD Chef and Pairs 树形DP

最新文章

热门文章