题解：P12136 [蓝桥杯 2025 省 B] 生产车间

ymx2009 · 2025-10-19 16:00:11 · 题解

题意化简

选择一些叶子节点，使得每个非叶子节点，它对应的子树中的已选叶子节点的权值和小于 w_i。
值得注意的是原题中一个点如果被删去了所有叶子节点，它并不会成为一个产出材料的叶子节点。

思路分析

设 f_i 表示 i 这个节点所有的可能取值，f_{i,j}=true 代表这个取值是可能的。
转移的复杂度为 O(nw^2)，但是因为有 s_1+s_2<w_i 的剪枝就可以通过此题。

Solution

朴素实现：

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,a[N];
bool f[N][N];
vector<int> e[N],tmp;

void dfs(int x,int fa)
{
    if(e[x].size()==1&&x!=1) f[x][a[x]]=true;//注意有可能是一条链
    f[x][0]=true;
    for(auto u:e[x])if(u!=fa)
    {
        dfs(u,x);
        tmp.clear();
        for(int i=0;i<=a[x];i++)if(f[x][i])for(int j=0;i+j<=a[x];j++)if(f[u][j]) tmp.push_back(i+j);
        for(auto y:tmp) f[x][y]=true;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1,x,y;i<n;e[x].push_back(y),e[y].push_back(x),i++) cin>>x>>y;
    dfs(1,0);
    for(int i=a[1];i>=0;i--)if(f[1][i])
    {
        cout<<i;
        return 0;
    }
}

已经可以通过此题，但是聪明的你发现这个 f_i 是可以使用 bitset 优化递推过程的。
bitset 优化实现：

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,a[N];
bitset<N> f[N];
vector<int> e[N];

void dfs(int x,int fa)
{
    if(e[x].size()==1&&x!=1) f[x].set(a[x]);//注意有可能是一条链
    f[x].set(0);
    for(auto u:e[x])if(u!=fa)
    {
        dfs(u,x);
        vector<bitset<N> > tmp;
        for(int i=1;i<=min(a[x],a[u]);i++)if(f[u][i]) tmp.push_back(f[x]<<i);
        for(auto y:tmp) f[x]|=y;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1,x,y;i<n;e[x].push_back(y),e[y].push_back(x),i++) cin>>x>>y;
    dfs(1,0);
    for(int i=a[1];i>=0;i--)if(f[1][i])
    {
        cout<<i;
        return 0;
    }
}