题意：
某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，
现在已知每个人的活跃指数和上司关系（当然不可能存在环），求邀请哪些人（多少人）来能使得晚会的总活跃指数最大。
#include <iostream>
#include <bits/stdc++.h>
const int maxn=6010;
using namespace std;
int dp[maxn][3],fa[maxn],vis[maxn];
vector<int> p[maxn];
void slove(int root){
vis[root]=1;
for(int i=0;i<p[root].size();i++){
if(vis[p[root][i]]==0){
slove(p[root][i]);
dp[root][1]=dp[root][1]+dp[p[root][i]][0];
dp[root][0]=dp[root][0]+max(dp[p[root][i]][1],dp[p[root][i]][0]);
}
}
return ;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>dp[i][1];
}
int b,c;
while(cin>>b>>c){
if(b==0&&c==0) break;
fa[b]=c;
p[c].push_back(b);
}
int m=fa[1],root;
while(m!=0)
root=m,m=fa[m];
slove(root);
cout<<max(dp[root][1],dp[root][0])<<endl;
return 0;
}
题意：
有n个点组成一棵树，问至少要删除多少条边才能获得一棵有p个结点的子树？
思路：
dp[root][j]：以root为根节点的子树，得到 j 个节点的子树需要最少减掉的边数，注意子树中必须保留root节点。否则无法dp
那么很明显的边界条件dp[root][1] = num（儿子的个数），因为要只剩一个节点的子树，那么所有的孩子都减掉，这样就为儿子的个数。
那么状态转移方程呢
dp[root][i] = min（dp[root][i-k]+dp[son][k] - 1，dp[root][i]）；
其实就是要得到一个i个节点的子树，枚举所有的孩子为k个节点的，当前root保留 i-k 个节点，然后把root和child之间之前被剪断的连接起来，所以这里要减1
树形dp 重要就是先解决子树 ，即c从下往上；
本题一个节点下有多个子节点（多个子树）； 先利用一个子节点更新答案，再利用另个子节点更新答案（此时，该节点已经使用上个子节点更新答案，）
所以满足逐个使用子节点更新答案； 当用完最后一个子节点；该节点答案已经完全；
所以slove函数中第二个循环j 从p开始（从大到小去找满足该子节点的结果）【若从小到大，就会出现在一层循环里（一个子节点），j=p-1 被j = p使用（小的已经算出，大的会用小的】
这样的话，在遍历其他子节点时，上个节点已经算出，会再次利用算出的值去计算
#include <iostream>
#include <bits/stdc++.h>
const int INF=0x3f3f3f3f;
using namespace std;
vector<int> v[200];
int dp[200][200],vis[200],fa[200],ru[200];;
int n,p;
void slove(int root){
vis[root]=1;
for(int i=0;i<v[root].size();i++){
if(!vis[v[root][i]]){
slove(v[root][i]);
for(int j=p;j>=1;j--){ // j从大到小
for(int k=1;k<j;k++){
dp[root][j]=min(dp[root][j],dp[root][j-k]+dp[v[root][i]][k]-1);
}
//cout<<root<<" "<<j<<" "<<dp[root][j]<<" "<<v[root][i]<<endl;
}
}
}
}
int main()
{
cin>>n>>p;
int nn=n;
int a,b;
n--;
memset(dp,INF,sizeof(dp));
memset(ru,0,sizeof(ru));
while(n--){
cin>>a>>b;
ru[a]++;
fa[b]=a;
v[a].push_back(b);
dp[a][0]=0;
dp[b][0]=0;
}
for(int i=1;i<=nn;i++) dp[i][1]=ru[i];
int m,root;
m=fa[1];root=1;
while(m!=0){
root=m;
m=fa[m];
}
//cout<<root<<endl;
slove(root);
int ans=dp[root][p];
cout<<dp[1][p];
for(int i=2;i<=nn;i++){
ans=min(ans,dp[i][p]+1);
}
cout<<ans<<endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int maxn=100100;
vector<int> g[maxn];
int sum[maxn],f[maxn],a[maxn],t[maxn];
int n;
void init(){
for(int i=1;i<=n;i++){
g[i].clear();
sum[i]=0;
f[i]=0;
}
}
void slove(int u,int par){
int t1=0,t2=0;
if (g[u].size() == 1 && par != -1) {
return;
}
for(int i=0;i<g[u].size();i++){
int x=g[u][i];
if(x==par) continue;
slove(x,u);
sum[u]+=f[x];
}
for(int i=0;i<g[u].size();i++){
int x=g[u][i];
if(x==par) continue;
t1=max(t1,sum[u]+a[x]);
}
int maxx=0,w=0;
for(int i=0;i<g[u].size();i++){
int x=g[u][i];
if(x!=par&&t[x]==3&&a[x]>maxx) {
maxx=a[x];w=x;
}
}
if(w!=0)
for(int i=0;i<g[u].size();i++){
int x=g[u][i];
if(x==par) continue;
if(w==x) continue;
t2=max(t2,a[w]+sum[x]-f[x]+a[x]+sum[u]);
}
for(int i=0;i<g[u].size();i++){
int x=g[u][i];
if(x==par) continue;
if(x==w) continue;
if(t[x]==3)
t2=max(t2,a[x]+sum[w]-f[w]+a[w]+sum[u]);
}
f[u]=max(t1,t2);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--){
cin>>n;
init();
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>t[i];
for(int i=1;i<=n-1;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
slove(1,-1);
cout<<f[1]+a[1]<<endl;
}
return 0;
}