```4 3
4 3 -2 1
1 2
2 3
3 4```

`7 1`

```6 8
-1 2 3 4 -5 6
1 4
4 5
4 6
5 6
5 2
2 3
5 3
3 6```

`11 4`

## 思路

（不用弄数组，因为你是 dfs，可以回溯）

（就是可能会有很多种链都是最大值）

## 代码

```#include<queue>
#include<cstdio>
#include<iostream>
#define ll long long

using namespace std;

struct node {
int to, nxt;
}e[100001];
int n, m, x, y, le[100001], KK, ru[100001], from[100001], now;
ll w[100001], ans1, ans2, sum[100001], minn[100001], re[100001], maxn[100001], rem[100001];
queue <int> q, ans;

void add(int x, int y) {
e[++KK] = (node){y, le[x]}; le[x] = KK;
}

void dfs(int now, ll qjh, ll minsum) {
ans2 = max(ans2, qjh - minsum);

if (rem[now] > qjh - minsum) return ;
rem[now] = qjh - minsum;

for (int i = le[now]; i; i = e[i].nxt)
dfs(e[i].to, qjh + w[e[i].to], min(minsum, qjh + w[e[i].to]));
}

int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
ru[y]++;
}

for (int i = 1; i <= n; i++) {
sum[i] = re[i] = -1ll << 50;
if (!ru[i]) {
q.push(i);
sum[i] = w[i];
minn[i] = min(0ll, w[i]);
re[i] = max(0ll, w[i]);
ans1 = max(re[i], ans1);
if (w[i] <= 0) from[i] = i;
else from[i] = 0;
}
}

while (!q.empty()) {
now = q.front();
q.pop();

for (int i = le[now]; i; i = e[i].nxt) {
if (re[e[i].to] <= sum[now] - minn[now] + w[e[i].to]) {
re[e[i].to] = sum[now] - minn[now] + w[e[i].to];
sum[e[i].to] = sum[now] + w[e[i].to];
if (sum[e[i].to] > minn[now]) from[e[i].to] = from[now];
else from[e[i].to] = e[i].to;
minn[e[i].to] = min(minn[now], sum[e[i].to]);
maxn[e[i].to] = max(maxn[now], sum[e[i].to] - minn[e[i].to]);

if (re[e[i].to] > ans1) {//找到有更优给 Monster 的
ans1 = re[e[i].to];
ans2 = maxn[from[e[i].to]];
//注意：这个不能是原来的 ans1，因为自己拿的和给 Monster 的要在同一条链上
while (ans.size()) ans.pop();
ans.push(e[i].to);//记录尾部
}
else if (re[e[i].to] == ans1) {//找到一样长的（可以给自己）
ans2 = max(ans2, maxn[from[e[i].to]]);//跟上面的一样要在同一条链上
ans.push(e[i].to);//记录所有最长的链的尾部
}
}

ru[e[i].to]--;
if (!ru[e[i].to]) q.push(e[i].to);
}
}

while (!ans.empty()) {
now = ans.front();
ans.pop();

for (int i = le[now]; i; i = e[i].nxt)
dfs(e[i].to, 0, 0);//在后面里看有没有更优的给自己的链
}

printf("%lld %lld", ans1, ans2);

return 0;
} ```