题干
You are given a tree consisting exactly of \(n\) vertices. Tree is a connected undirected graph with \(n−1\) edges. Each vertex \(v\) of this tree has a value \(a_v\) assigned to it.
- Let \(dist(x,y)\) be the distance between the vertices \(x\) and \(y\). The distance between the vertices is the number of edges on the simple path between them.
- Let's define the cost of the tree as the following value: firstly, let's fix some vertex of the tree. Let it be \(v\). Then the cost of the tree is \(\sum\limits_{
- i=1
- }^{
- n
- }dist(i, v)a_i\)
- Your task is to calculate the maximum possible cost of the tree if you can choose \(v\) arbitrarily.
- \(\mathcal{
- Input
- }\)
- The first line contains one integer \(n\), the number of vertices in the tree \((1\leq n\leq 210^5)\).
- The second line of the input contains \(n\) integers \(a_1,a_2, \cdots ,a_n \; (1\leq a_i\leq 210^5)\), where \(a_i\) is the value of the vertex \(i\).
- Each of the next \(n−1\) lines describes an edge of the tree. Edge \(i\) is denoted by two integers \(u_i\) and \(v_i\), the labels of vertices it connects \((1\leq u_i,v_i\leq n, u_i\not= v_i).\)
It is guaranteed that the given edges form a tree.
- \(\mathcal{
- Output
- }\)
- Print one integer - the maximum possible cost of the tree if you can choose any vertex as \(v\).
- \(\mathcal{
- Example
- }\)
- \(Case_1\)
- \(Input\)
- 8
- 9 4 1 7 10 1 6 5
- 1 2
- 2 3
- 1 4
- 1 5
- 5 6
- 5 7
- 5 8
- \(Output\)
- 121
- \(Case_2\)
- \(Input\)
- 1
- 1337
- \(Output\)
- 0
- \(\mathcal{
- Note
- }\)
- Picture corresponding to the first example:
- You can choose the vertex \(3\) as a root, then the answer will be \(29+14+01+37+310+41+46+45=18+4+0+21+30+4+24+20=121\).
- In the second example tree consists only of one vertex so the answer is always \(0\).
- \(\mathcal{
- Tag
- }\)
- dfs and similar dp tree *1800
思路分析
本题要求解的是, 对于树中所有结点, 以该节点为根的情况下计算费用, 并求费用的最大值. 注意在结点非常多的情况下, 要考虑 \(int\) 溢出的问题, 故开 \(long\;long\)(坑死我了)
暴力想法
暴力想法很简单, 很类似 CF1324 --- Maximum White Subtree, 这里直接搬运那个题解里面的图片
对于任意结点, 分别计算不同路径的位置, 根据树数据结构的特点, 可以把贡献分为:
上层父祖先节点贡献
下层子孙结点贡献
然后就是, 如何把暴力 \(dfs\), 通过记忆化实现算法优化.
算法优化
我们先求解下层子孙结点的贡献, 通过题目我们知道, 从结点 \(v\) 转移到结点 \(u\), 其中增量的就是以 \(v\) 为根结点, 其子树中所有结点值的和. 其中 \(a_i\) 代表结点 \(i\) 的值, 我们设 \(f_i\) 代表以 \(i\) 结点为子树根结点, 该子树所有结点的和. 我们设 \(hp_i\) 代表以 \(i\) 结点的下层子孙贡献值, 这样我们可以写出下层子孙结点贡献值的转移表达值:
- \[f[u] = f[v] + a[u] \]
- \[hp[u] = hp[v] + f[v] \]
现在我们解决了下层得想办法解决更加困难的上层了, 对于这类换根 dp 问题, 常用的手段是用利用父节点的值进行状态转移. 在这里我们设 \(dp_i\) 为结点 \(i\) 的最终费用. 因此对于某一节点 (非根结点), 该节点的最终费用可以表示为:
\[dp[cur] = dp[fa] - hp[cur] - f[cur] + f[fa] - f[cur] + hp[cur] = dp[fa] + f[fa] - 2*f[cur] \]
上述表达式的意思为: 父节点刨去结点 \(cur\) 的费用值 (\(dp[fa] - hp[cur] - f[cur]\), 加上增量 (\(f[fa] - f[cur]\), note 这里的 f[fa], 代表着所有的结点和), 再最后加上下层子孙结点贡献值 (\(hp[cur]\)).
\[1dp[v] = \left\{\begin{array} hp[v] & if\; v = root \\ dp[fa] + f[fa] - 2*f[v] & if\; v \not= root\\ \end{array}\right. \]
&emps; 因此我们最终的思路还是为:
从下往上树形 \(dp\), 计算 \(f_v\),\(hp_v\)
从上往下换根 \(dp\), 计算 \(dp_v\)
代码
- #include<bits/stdc++.h>
- using namespace std;
- using LL = long long;
- using VL = vector<LL>;
- using VVL = vector<VL>;
- LL mx = 0x8000000000000000;
- VL a, f, hp, dp;
- VVL e;
- void dfs(int x, int fa = -1)
- {
- f[x] = a[x], hp[x] = 0;
- for (auto to : e[x])
- {
- if (to == fa) continue;
- dfs(to, x);
- f[x] += f[to];
- hp[x] += (hp[to] + f[to]);
- }
- }
- void rdfs(int x, int fa = -1)
- {
- dp[x] = hp[x];
- mx = max(mx, dp[x]);
- for (auto to : e[x])
- {
- if (to == fa) continue;
- hp[to] = dp[x] + f[x] - 2*f[to];
- f[to] = f[x];
- rdfs(to, x);
- }
- }
- int main()
- {
- int n;
- cin>> n;
- cout <<mx << endl;
- a = f = hp = dp = VL(n);
- e = VVL(n);
- for (auto &x : a) cin>> x;
- for (int i = 0; i <n - 1; ++ i)
- {
- int x, y;
- cin>> x>> y;
- -- x, -- y;
- e[x].push_back(y);
- e[y].push_back(x);
- }
- dfs(0);
- rdfs(0);
- cout << mx << endl;
- return 0;
- }
做了两次了, 这个 1092 是自己手打的, 还是有进步. WA 了一次是没有考虑到整数溢出的情况以后得多加考虑.
以后对于每个根结点都要求的题, 考虑优先换根 dp.
来源: https://www.cnblogs.com/Last--Whisper/p/12817501.html