[CF1220E] Tourism

[CF1220E] Tourism - DFS树

Description

有 (n) 个点， (m) 条边的简单无向图。每个点有一个权值 (w_i) 。一个人从 (s) 出发，可以走一条不走回头路的路径。也就是不能经过一条边立刻反着走，但是允许重复经过边即如果从 (u) 走向 (v) ，那么不能从 (v) 走向 (u) 。最大化权值和。

Solution

如果 DFS 树上，p 的子树内有环，那么 p 肯定能被选中

对于其它的点，我们只能选出一条最长链

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6 + 5;

int n, m, w[N], f[N], tag[N], vis[N];
vector<int> g[N];
int s;

void dfs(int p, int from)
{
    vis[p] = 1;
    for (int q : g[p])
    {
        if (q == from)  
            continue;
        if (vis[q])
            tag[p] = 1;
        else
        {
            dfs(q, p);
            tag[p] |= tag[q];
        }
    }
    if (tag[p] == 0)
    {
        for (int q : g[p])
        {
            if (q == from)
                continue;
            f[p] = max(f[p], f[q]);
        }
        f[p] += w[p];
    }
}

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> s;
    dfs(s, 0);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (tag[i] == 0)
            ans = max(ans, f[i]);
    for (int i = 1; i <= n; i++)
        if (tag[i] == 1)
            ans += w[i];
    cout << ans << endl;
}