题目描述：
现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。
每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。
给定路径的 价格总和 是该路径上所有节点的价格之和。
另给你一个二维整数数组 trips ，其中 trips[i] = [starti, endi] 表示您从节点 starti 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 endi 。
在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。
返回执行所有旅行的最小价格总和。
数据范围：
$1\le n \le 50, 1\le price[i] \le 1000, 1\le trips.len \le 100$
题解：
dfs加树形dp：
可以先对每个旅行进行 dfs，遍历出来经过的点，更新经过点的频率 freq[u]。最终的答案就是 $\sum freq[i] \times price[i]$ 。
下面需要考虑对哪些节点进行减半操作。假设 $dp[u][0/1]$ 分别表示对 $u$ 节点不减半和减半之后的最小价值。则 $u$ 不减半，那么 $v$ 可以减半，也可以不减半， $dp[u][0] = dp[u][0] + \min(dp[v][0], dp[v][1])$ ； $u$ 减半的话， $v$ 只能不减半，可以得到 $dp[u][1] = dp[u][1] + dp[v][0]$ 。注意每个节点的初始化，初始时 $dp[u][0] = freq[u] \times price[u], dp[u][1] = \frac{dp[u][0]}{2}$ .
LCA+树上差分+树形dp：
可以使用倍增法求出 $x, y$ 的 $LCA(x, y) = z$ 。使用差分计算频率，对 $x\rightarrow z, z \rightarrow y$ 路径上加 $1$ ，可以对 $cnt[z]+1, cnt[son[x]]-1, cnt[son[y]]-1$ 。
也可以对 $cnt[x]+1, cnt[y] + 1, cnt[z]-1, cnt[fa[z]]-1$ 。因为需要把 $z$ 也加一次，所以只能对 $z$ 加两次，减一次，然后对父亲减一次。下面这种使用的比较多。
因为下标是从 $0$ 开始的，可以先判断一下 $fa[lca][0]$ 是不是 $lca$ ，如果是的话，说明是根节点，就不用减父节点了。最后用一个 dfs 求出来所有点的权值和，从下往上求。
然后使用树形dp，求解最小价值。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<vector<int>> g;
vector<int> freq;
vector<vector<int>> dp;
bool find;
bool dfs(int u, int fa, int end)
{
freq[u]++;
if (u == end)
find = true;
if (find)
return true;
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
if (v == fa)
continue;
if (dfs(v, u, end))
return true;
}
freq[u]--;
return false;
}
void dfs2(int u, int fa, vector<int> &price)
{
dp[u][0] = freq[u] * price[u];
dp[u][1] = dp[u][0] >> 1;
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
if (v == fa)
continue;
dfs2(v, u, price);
dp[u][0] += min(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
int minimumTotalPrice(int n, vector<vector<int>> &edges, vector<int> &price, vector<vector<int>> &trips)
{
g.resize(n);
freq.resize(n);
dp.resize(n, vector<int>(2));
for (auto &edge : edges)
{
int u = edge[0], v = edge[1];
g[u].emplace_back(v);
g[v].emplace_back(u);
}
for (auto &trip : trips)
{
find = false;
dfs(trip[0], -1, trip[1]);
}
dfs2(0, -1, price);
return min(dp[0][0], dp[0][1]);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<vector<int>> g;
vector<vector<int>> fa;
vector<int> freq;
vector<vector<int>> dp;
vector<int> dep;
vector<int> log2;
void dfs(int u, int fa)
{
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
if (v == fa)
continue;
dep[v] = dep[u] + 1;
this->fa[v][0] = u;
dfs(v, u);
}
}
void dfs2(int u, int fa, vector<int> &price)
{
dp[u][0] = freq[u] * price[u];
dp[u][1] = dp[u][0] >> 1;
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
if (v == fa)
continue;
dfs2(v, u, price);
dp[u][0] += min(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
void dfs3(int u, int fa)
{
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
if (v == fa)
continue;
dfs3(v, u);
freq[u] += freq[v];
}
}
int query(int x, int y)
{
if (dep[x] < dep[y])
swap(x, y);
int tmp = dep[x] - dep[y];
while (dep[x] != dep[y])
{
x = fa[x][log2[tmp]];
tmp -= (1 << log2[tmp]);
}
if (x == y)
return x;
for (int i = log2[dep[x]]; i >= 0; --i)
{
if (fa[x][i] != fa[y][i])
{
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
int minimumTotalPrice(int n, vector<vector<int>> &edges, vector<int> &price, vector<vector<int>> &trips)
{
g.resize(n);
freq.resize(n);
dep.resize(n);
dp.resize(n, vector<int>(2));
fa.resize(n, vector<int>(7));
log2.resize(n + 1);
for (int i = 2; i <= n; ++i)
log2[i] = log2[i >> 1] + 1;
for (auto &edge : edges)
{
int u = edge[0], v = edge[1];
g[u].emplace_back(v);
g[v].emplace_back(u);
}
dfs(0, -1);
for (int i = 1; i <= 6; ++i)
{
for (int u = 0; u < n; ++u)
{
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
}
for (auto &trip : trips)
{
int lca = query(trip[0], trip[1]);
freq[trip[0]]++;
freq[trip[1]]++;
freq[lca]--;
if (fa[lca][0] != lca)
freq[fa[lca][0]]--;
}
dfs3(0, -1);
dfs2(0, -1, price);
return min(dp[0][0], dp[0][1]);
}
};
|