没有上司的舞会

都是基础啊,因为我也才刚学.
凡是涉及树形dp,你就得先知道怎么转移.
一般dp问题是解决max/min.那么这个dp问题也是解决max和min,但是怎么解决呢?
很容易想到这个dp的表示方式.
开两维:dp[u][0/1]表示以u为根节点的子树,选不选u节点所获得的最大权值,然后配合dfs更新子树信息转移即可.转移方程大概是:

假设u节点的子节点为x.
dp[u][1]=max(dp[u][1],w[u]+dp[x][0]);
dp[u][0]=max(dp[u][0],dp[x][1]);

然后就是写代码了..
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=6e3+5;
vector<int>v[N];
int w[N];
int dp[N][2];
inline void dfs(int u,int s)//儿子 父亲
{
    for(int i=0;i<v[u].size();i++)
    {
        int x=v[u][i];
        if(s==x) continue;
        dfs(x,u);
        dp[u][1]+=dp[x][0];
        dp[u][0]+=max(dp[x][1],dp[x][0]);
    }
    dp[u][1]+=w[u];
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    /*
    for(int i=0;i<v[4].size();i++)
    {
        cout<<v[4][i]<<' ';
    }cout<<endl;*/
    //cout<<dp[4][0]<<endl;
    cout<<max(dp[1][0],dp[1][1])<<endl;
    return 0;
}
/*
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
*/