P1453 城市环路

题目大意

给定一棵基环树，选取一个点集，使得点集中的任意两点之间没有直接的连边，最大化 $\sum_{u \in S} p_u \times k$ 。

解题思路

我们先找到这个基环树的环，然后随便找环上相邻的两点，假设为 $u, v$ ，那么我们断开 $u, v$ 这条边，分别以 $u, v$ 为根跑 DP：

\begin{aligned} dp_{u, 0} &= \sum_{v \in son(u)} \max(dp_{v, 0}, dp_{v, 1}) \\ dp_{u, 1} &= \sum_{v \in son(u)} dp_{v, 0} \end{aligned}

然后我们考虑最后的结果要么是取 $u$ 不取 $v$ ，要么是取 $v$ 不取 $u$ ，取最大值即可。

代码

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
constexpr int N = 1e5 + 5;
6

7
int n, u, v, p[N], rt_u, rt_v;
8
long long dp[N][2];
9
bool vis[N];
10

11
vector<int> adj[N];
12

13
inline bool get_loop(int u, int fa) {
14
  vis[u] = true;
15

16
  for (auto v : adj[u]) {
17
    if (v == fa) continue;
18
    if (vis[v]) {
19
      rt_u = u, rt_v = v;
20
      return true;
21
    }
22
    if (get_loop(v, u)) return true;
23
  }
24
  return false;
25
}
26

27
inline void dfs(int u, int fa, int rt_u, int rt_v) {
28
  dp[u][0] = 0;
29
  dp[u][1] = p[u];
30

31
  for (auto v : adj[u]) {
32
    if (v == fa) continue;
33
    if ((u == rt_u && v == rt_v) || (v == rt_u && u == rt_v)) continue;
34

35
    dfs(v, u, rt_u, rt_v);
36

37
    dp[u][0] += max(dp[v][0], dp[v][1]);
38
    dp[u][1] += dp[v][0];
39
  }
40
}
41

42
int main() {
43
  ios::sync_with_stdio(false);
44
  cin.tie(nullptr);
45
  cout.tie(nullptr);
46

47
  cin >> n;
48

49
  for (int i = 1; i <= n; i++)
50
    cin >> p[i];
51

52
  for (int i = 1, u, v; i <= n; i++) {
53
    cin >> u >> v;
54
    u++, v++;
55
    adj[u].push_back(v);
56
    adj[v].push_back(u);
57
  }
58

59
  double k;
60
  cin >> k;
61

62
  get_loop(1, 0);
63

64
  long long ans = 0;
65

66
  dfs(rt_u, 0, rt_u, rt_v);
67
  ans = max(ans, dp[rt_u][0]);
68

69
  dfs(rt_v, 0, rt_u, rt_v);
70
  ans = max(ans,dp[rt_v][0]);
71

72
  cout << setiosflags(ios::fixed) << setprecision(1) << (double) ans * k << "\n";
73

74
  return 0;
75
}