给出多棵有n个节点的有根树，第i个节点有一个权值\(a_i\)，定义一个点能控制的点为其所有的子节点和它自己，询问选出若干个点的最少的权值之和，并且能够控制大于等于m个点，\(1 ≤ n ≤ 200\)

解

此题卡输入，插点题外话

---

c++语法讲解：

1. c++11将gets()函数弃用了，而代以更加安全的fgets()，原因为gets的读入为一定要读完一行，而实际上可以读的数据是无限的，而电脑的内存空间是有限的，用无限的数据去填满有限的内存，那是自然会死机的，于是fgets加了一个限制，一定要按你给的字符数组大小读入，自然不支持string。

2. fgets(char数组名,sizeof(char数组名),stdin)

3. streamstring是为了方便读入而引入的，比较老的c++版本是不会支持的，但放心的是oi肯定支持（类似一个类型）

4. 用法（建议运行试一试）

参考代码

#include 
    
     #include 
     
      #include 
      
       using namespace std;int main(){    char s[1000];    stringstream a;//a为变量名//读入7 afsfs 0.125    fgets(s,sizeof(s),stdin);    a.clear(),a.str(s);//清空a，用s来填充a    int b;string c;double d;    a>>b,a>>c,a>>d;    cout<
       <<' '<
        
         <<' '<
        
      
     
    

• .clear()

清空状态标志，每次用完stringstream一定要清空，但未释放内存，可以做个小测试，打开内存显示，运行一下下面的程序，等待5s

#include 
    
     #include 
     
      #include 
      
       using namespace std;int main(){    register stringstream io;    while(true)io<<"lsy akioi",io.clear();    return 0;}
      
     
    

• .str()

用字符串s来重置stringstream,释放了内存

• \(>>,<<\)分别表示输入到和输出到

废话完结

---

回到题目，显然是树形递推，因为是森林，故用一个超级根0连上所有树根，变为一棵树，肯定设两维\(f[i][j]\)表示以i为节点的子树中，控制了j个点的选择权值之和的最小值，显然有

\[f[i][j]=f[i][j-k]+f[l][k]\]

其中l为i的一个子节点，k为其控制的点，也可以用分组背包来理解，i只不过代替不同的背包，j是容量，而子树就是每一组物品，k就是物品，只是压了子树这一维状态,设\(s[x]\)为x的子树中节点个数。

边界：\(f[x][0]=0,f[x][s[x]]=a_x,x=0,1,2,3,...,n\)特别地\(a_0=INT\_MAX\)。

参考代码：

#include 
    
     #include 
     
      #include