1 条题解

  • 0
    @ 2023-10-4 8:33:06
    #include <iostream>
    #include<vector>
    using namespace std;
    
    const int N = 1e4 + 10;
    vector<int> tr[N];
    int f[N][2], v[N], Happy[N], n;
    void dfs(int u)
    {
        f[u][0] = 0;
        f[u][1] = Happy[u];
        for (auto v : tr[u]) 
        {
            dfs(v);
            f[u][0] += max(f[v][0], f[v][1]);
            f[u][1] += f[v][0];
        }
    }
    int main() {
        cin.tie(nullptr)->sync_with_stdio(false);
        cin >> n; 
        for (int i = 1; i <= n; ++i)
            cin >> Happy[i];
        for (int i = 1, x, y; i < n; ++i)
        {
            cin >> x >> y; 
            v[x] = 1;
            tr[y].push_back(x);
        }
        int root;
        for (int i = 1; i <= n; ++i)
        {
            if (!v[i])
            {
                root = i;
                break; 
            }
        }
        dfs(root);
        cout << max(f[root][0], f[root][1]) << "\n";
    }
    
  • 1

信息

ID
1548
时间
1000ms
内存
256MiB
难度
9
标签
递交数
11
已通过
6
上传者