思路

https://www.luogu.com.cn/problem/P12136
十六届C++ B最难的一道题目，正解是使用树上dp，但是没学。使用基于set的dfs()求解，类似dp的思想。同时用到了之前类似树形图的存储方式。

仅仅计算子树可能提供的最大流量是不够的。因为将多个子节点的最大流量组合可能会超过父节点的容量 w_p。 如果发生这种情况，必须减少或消除一个或多个子节点的贡献。我们无法预先知道应该减少或消除哪个子节点的贡献。

因此，我们不能存储子树可能提供的最大输出，而是存储子树可以提供的所有可能的有效输出的集合。

在遍历所有子节点 v 后，最终的集合 s 包含所有可能的输入值 I ，使得节点u从其子节点接收的 I <= w[u] ，并且下方u的所有约束也得到满足（因为递归调用返回的集合t已经保证了这一点）。这些值I正是节点u可以向上传递给其父节点的可能流量。

#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;

const int N = 1010;
int w[N]; //节点的权重
vector<int> e[N]; //存储边的关系（无边权重）
int n;

set<int> dfs(int cur, int last)
{
    if(e[cur].size()==1 && cur!=1) //叶子结点
        return {0,w[cur]};//删或不删

    //对于非叶子节点
    set<int> cur_res = {0};//所有子节点到u的可能输入集合，0表示删除整个
    for(auto ele : e[cur]) //遍历当前节点的子节点
    {
        if(ele == last) //防止回溯搜索
            continue;
        auto ele_res = dfs(ele,cur); //搜索子节点的可能向上传递集合
        auto cur_res_cpy = cur_res; //基于目前搜索到的子节点的本节点所有可能向上传递集合
        //使用s的copy是为了避免动态更新的s会发生重复判断

        for(auto x : cur_res_cpy)
            for(auto y : ele_res) //两两组合更新
            {
                if(x+y > w[cur]) //不合法
                    break; //set是升序排序，直接跳出
                else
                    cur_res.insert(x+y); //如果重复就会自动忽略
            }
    }
    return cur_res;//返回所有子节点所有可能的向上传递的集合（也是当前节点向上传递的集合）
}

int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i ++)
        scanf("%d",&w[i]);
    for(int i = 0; i < n-1; i ++)
    {
        int st,ed;
        scanf("%d%d",&st,&ed);
        e[st].push_back(ed);
        e[ed].push_back(st);
    }

    auto res_set = dfs(1,0);

    int Max = 0;
    for(auto ele : res_set) //找出最大的
        Max = max(ele,Max);
    printf("%d",Max);
    return 0;
}