Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

树形dp，拓扑排序遍历树

Posted by On18 at 2020-05-18 16:27:17 on Problem 2342
```#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
int n;
while (cin >> n)
{
vector<int> rate(n + 1);
vector<int> sup(n + 1);
vector<int> in(n + 1);
vector<vector<int>> dp(2, vector<int>(n + 1));
for (int i = 1; i <= n; ++i)
scanf("%d", &rate[i]);
int a, b;
while (scanf("%d %d", &a, &b) && a && b)
{
sup[a] = b;
in[b] += 1;
}
queue<int> q;
for (int i = 1; i <= n; ++i)
if (in[i] == 0)
q.push(i);
int x;
while (!q.empty())
{
x = q.front();
q.pop();
dp[1][x] += rate[x];
int sx = sup[x];
dp[1][sx] += max(dp[0][x], 0);
dp[0][sx] += max(0, max(dp[1][x], dp[0][x]));
in[sx] -= 1;
if (in[sx] == 0 && sx > 0)
q.push(sx);
}
cout << max(dp[0][x], dp[1][x]) << endl;
}
}```

Followed by: