题解 CF1220E 【Tourism】
jasonleft
2020-02-04 01:28:46
# 缩点 + 树DP
## 题意:
- 有一个$n(n\le 2\times 10^5)$点$m(m\le 2\times 10^5)$ 边的无重边无自环的无向图，每个点有个点权。从 1 出发，不能连续经过同一条边，问路径上点权和的最大值是多少。(抄楼上)
### 数据范围: rt
### **Tutorial:**
如果遇到了环, 我们一定可以把它算到贡献里面(走一圈再出来), 所以可以考虑缩点....
缩点以后得到若干树, 我们只关心包含起点的那颗, 然后就是愉快的树形dp了
$f[cur]$代表走到cur子树还能回的贡献
$g[cur]$代表走到cur子树回不来的贡献
目标:$g[s]$
先考虑$f$的转移, 如果子节点能回来:$f[cur]+=f[to]$
然后$g[cur] = max(g[to]) + f[cur]$走完所有可以返回的儿子再找个最大的不能返回的
...
你以为完了吗,
这样有一个问题, 如果$f[cur] < g[cur]$ - 结点cur是否要返回
于是再 :
$g[cur] = max(g[cur], f[cur] - f[to] + g[to]);$
```cpp
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define _rep(n, a, b) for (ll n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (ll n = (a); n >= (b); --n)
#define _for(n, a, b) for (ll n = (a); n < (b); ++n)
#define _rof(n, a, b) for (ll n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3f
#define ll long long
#define db double
#define eps 1e-8
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll maxn = 4e5 + 5;
struct node
{
ll nxt, to;
} way[maxn];
ll cnt, head[maxn], dfn[maxn], tim, low[maxn], val[maxn], st[maxn], top, node_num, bel[maxn], w[maxn], sz[maxn];
void addedge(ll from, ll to)
{
way[++cnt].to = to;
way[cnt].nxt = head[from];
head[from] = cnt;
}
ll n, m;
struct edge {
ll from, to;
edge(ll _from = 0, ll _to = 0):from(_from), to(_to){}
bool operator <(const edge& a) {
return from == a.from ? to < a.to : from < a.from;
}
bool operator ==(const edge& a) {
return from == a.from && to == a.to;
}
};
vector<ll> G[maxn];
vector<edge> tmp;
void tarjan(ll cur, ll fa)
{
dfn[cur] = low[cur] = ++tim;
st[++top] = cur;
for (ll i = head[cur]; i; i = way[i].nxt)
{
ll to = way[i].to;
if (to == fa)
continue;
if (!dfn[to])
{
tarjan(to, cur);
low[cur] = min(low[cur], low[to]);
}
else if (!bel[to])
low[cur] = min(low[cur], dfn[to]);
}
if (dfn[cur] != low[cur])return;
node_num++;
while (st[top] != cur) bel[st[top--]] = node_num;
bel[st[top--]] = node_num;
}
void build() {
_rep(i, 1, n) {
val[bel[i]] += w[i];
sz[bel[i]]++;
}
_rep(i, 1, n) {
for (ll j = head[i]; j; j = way[j].nxt) {
ll to = way[j].to;
if (bel[i] == bel[to])continue;
tmp.push_back(edge(bel[i], bel[to]));
}
}
sort(all(tmp));
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
for (auto i : tmp) {
G[i.from].push_back(i.to);
}
}
ll f[maxn], g[maxn];
bool ret[maxn];
void dfs(ll cur, ll fa) {
f[cur] = val[cur];
if (sz[cur] > 1)ret[cur] = 1;
ll mx = 0;
for (auto to : G[cur]) {
if (to == fa)continue;
dfs(to, cur);
if (ret[to])f[cur] += f[to], ret[cur] = 1;
else mx = max(mx, g[to]);
}
g[cur] = f[cur] + mx;
for (auto to : G[cur]) {
if (to != fa && ret[to])
g[cur] = max(g[cur], f[cur] - f[to] + g[to]);
}
}
signed main()
{
cin >> n >> m;
_rep(i, 1, n)cin >> w[i];
_rep(i, 1, m)
{
ll u, v;
cin >> u >> v;
addedge(u, v);
addedge(v, u);
}
ll s;
cin >> s;
_rep(i, 1, n) if (!dfn[i]) tarjan(i, 0);
build();//缩点系列
dfs(bel[s], 0);
cout << g[bel[s]] << endl;
}
```