树形DP->没有上司的舞会(洛谷1352)

题意：每个人有一个happ值，n个人，n - 1条有向边，u是v的上司，求happy值最大。 限制条件是u和v不能同时参加。

分析：没想到一个v居然有很多上司，更没想到n-1条边居然是个森林。

//没想到，一个员工居然可以有那么多上司。。
void solve(){
    int n;
    cin >> n;

    vector<int> happy(n + 1);
    for (int i = 1; i <= n; ++i){
        cin >> happy[i];
    }

    vector<int> indegree(n + 1);
    vector<vector<int>> al(n + 1);
    for (int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        swap(u, v);
        indegree[v] ++;
        al[u].emplace_back(v);
    }

    int root = 0;
    for (int i = 1; i <= n; ++i){
        if (indegree[i] == 0){
            al[0].emplace_back(i);
        }
    }

    vector<array<int, 2>> dp(n + 1);
    function<void(int, int)> dfs = [&](int u, int p){
        dp[u][1] = happy[u];
        dp[u][0] = 0;
        for (const auto& v : al[u]){
            if (v != p){
                dfs(v, u);
                dp[u][0] += max(dp[v][1], dp[v][0]);
                dp[u][1] += dp[v][0];
            }
        }
    };

    dfs(0, -1);

    int ans = 0;
    for (auto& v : al[0]){
        ans += max(dp[v][0], dp[v][1]);
    }

    cout << ans << '\n';
}