湖南移动官网网站建设,做网站哪家便宜厦门,我的文档上传到网站 做链接,如何制作微信公众号微商城题目
1.最长乘积链 - 蓝桥云课 (lanqiao.cn)
初始思路
对问题进行分析#xff0c;对每个点dfs去求走不同路的最远距离与次远距离求乘积#xff0c;时间复杂度为O(n^2)
看了答案怎么弄的优化
解题思路
总的来说
预处理#xff08;对每个结点的信息进行统计#xff09…题目
1.最长乘积链 - 蓝桥云课 (lanqiao.cn)
初始思路
对问题进行分析对每个点dfs去求走不同路的最远距离与次远距离求乘积时间复杂度为O(n^2)
看了答案怎么弄的优化
解题思路
总的来说
预处理对每个结点的信息进行统计预处理完后对所有节点遍历去求乘积最大值
在确定树的拓扑结构后单独求一个节点的最远距离时会在该树上去比较得到如下路径
从当前节点往下直到子树中某个节点的最长路径。从当前节点往上走到其父节点再从其父节点出发且不回到该节点的最长路径。
也就是先向上走与先向下走。两个方向上的最长路径相乘就是答案。
每个合法节点能贡献二个乘积向下走的最远距离乘次远距离和向上走的最远距离乘向下走的最远距离。
处理次大值的原因是
当我们求向上走的最大值时原理为我到父结点的距离加上父结点到别的点的最远距离如果父结点到别的点的最远距离经过我时则不能使用此时就得变成我到父结点的距离加上父结点到别的点的次远距离。因为别一个乘积为从父到根的距离不一定是最优的。
树形DP
我们在此引入 树形DP 解题
指定任意一个根节点。一次dfs 遍历统计出每个点向下走的最大值与次大值以及最大值下去的方向与次大值下去的方向最大值和次大值走的不是同一方向。一次 dfs 遍历统计出先向上走的最大值。
最大值与次大值更新原理为当前结点到子节点的距离加上子节点到叶子结点的最远距离我们对这些子结点求最大值与次大值即可
整体思路 标注
如何记录方向记录以 i 出发的最近子节点是什么 代码
#include iostream
#include vector
#include algorithm
using namespace std;const int N 100010;
vectorpairint, int g[N];
int d1[N], d2[N], up[N], p1[N], p2[N];
int n, m, k;void dfs1(int u, int f) {for (auto v : g[u]) {if (v.first f) continue;dfs1(v.first, u); //先到叶子后转移if (d1[v.first] v.second d1[u]) { //叶子的d1d2都是0如果可转移则相加转移d2[u] d1[u];p2[u] p1[u];d1[u] d1[v.first] v.second;p1[u] v.first;} else if (d1[v.first] v.second d2[u]) {d2[u] d1[v.first] v.second;p2[u] v.first;}}
}void dfs2(int u, int f) {for (auto v : g[u]) {if (v.first f) continue;if (p1[u] v.first)up[v.first] v.second max(up[u], d2[u]);elseup[v.first] v.second max(up[u], d1[u]);dfs2(v.first, u);}
}int main() {int t 1;for (int zu 1; zu t; zu) {cin n;for (int i 1; i n - 1; i) {int a, b, c;cin a b c;g[a].push_back(make_pair(b, c));g[b].push_back(make_pair(a, c));}dfs1(1, -1);dfs2(1, -1);long long res 0;for (int i 1; i n; i) {res max(res, max(1LL * d1[i] * d2[i], 1LL * d1[i] * up[i]));}cout res endl;}return 0;
}
