树上倍增求链上最大值或最小值

蔚落 2023-06-01 15:00 71阅读 0赞

倍增求链上点最大值

inline int LCA(int x,int y) { int maxn=max(w[x],w[y]); if (deep[x]>deep[y]) swap(x,y); int k=log2(deep[y]); for (int i=k;i>=0;i--) if (deep[f[i][y]]>=deep[x]) { maxn=max(maxn,maxx[i][y]); y=f[i][y]; } if (x==y) return max(maxn,w[x]); for (int i=k;i>=0;i--) if (f[i][y]!=f[i][x]) { maxn=max(maxn,maxx[i][x]); maxn=max(maxn,maxx[i][y]); y=f[i][y]; x=f[i][x]; } return max(maxn,maxx[0][x]); } inline void dfs(int x,int fa) { deep[x]=deep[fa]+1; f[0][x]=fa; maxx[0][x]=w[fa]; for (int i=1;(1<<i)<=deep[x];i++) { f[i][x]=f[i-1][f[i-1][x]]; maxx[i][x]=max(maxx[i-1][x],maxx[i-1][f[i-1][x]]); } for (int i=head[x];i;i=ed[i].next) if (ed[i].e!=fa) dfs(ed[i].e,x); return ; }

倍增求链上边最大值

inline int LCA(int x,int y) { int maxx=0; if (deep[x]>deep[y]) swap(x,y); int k=log2(deep[y]); for (int i=k;i>=0;i--) if (deep[f[i][y]]>=deep[x]) { maxx=max(maxv[i][y],maxx); y=f[i][y]; } if (x==y) return maxx; for (int i=k;i>=0;i--) if (f[i][y]!=f[i][x]) { maxx=max(maxv[i][y],maxx); maxx=max(maxv[i][x],maxx); y=f[i][y]; x=f[i][x]; } return max(maxx,max(maxv[0][x],maxv[0][y])); } inline void dfs2(int x,int fa) { f[0][x]=fa; for (int i=1;(1<<i)<=deep[x];i++) { f[i][x]=f[i-1][f[i-1][x]]; maxv[i][x]=max(maxv[i-1][x],maxv[i-1][f[i-1][x]]); } for (int i=head[x];i;i=ed[i].net) if (ed[i].e!=fa) dfs2(ed[i].e,x); return ; } inline void dfs1(int x,int fa) { deep[x]=deep[fa]+1; for (int i=head[x];i;i=ed[i].net) if (ed[i].e!=fa) dfs1(ed[i].e,x); else maxv[0][x]=ed[i].v; return ; }

转载于:https://www.cnblogs.com/last-diary/p/11260680.html

发表评论取消回复

表情：

评论列表（有 0 条评论，71人围观）

还没有评论，来说两句吧...

相关阅读

相关【树上倍增】最小瓶颈生成树

随便学一下树上倍增，反正闲着也是闲着一周没vpCf，感觉早该414了下周vp abc！至少能开出签到呜呜呜 [【模板】最小瓶颈生成树（数据加强版） - 题目 -

r囧r小猫/ 2024年03月25日 20:16/ 0 赞/ 144 阅读

相关分治法求最大最小值

分治法是一种递归的问题解决方法，它将一个大问题划分为多个小问题，然后逐个解决这些小问题，最后将结果合并得到最终的解决方案。对于求最大最小值的问题，可以使用分治法来解决。以下

绝地灬酷狼/ 2024年02月20日 12:42/ 0 赞/ 186 阅读

相关【c语言】求最大最小值

问题描述　　给定 N 个整数，请你找出这 N 个数中最大的那个和最小的那个。　　输入格式　　第一行包含一个正整数 N 。(1 ≤ N ≤ 10000)。

￡神魔★判官ぃ/ 2023年07月15日 18:26/ 0 赞/ 109 阅读

相关 mysql 求最小值/最大值

计算所有人最低工资和最高工资,需分别用到min()和max()函数。(请注意，MIN和MAX函数会忽略NULL值) 1 select min(sal) as min\_s

淩亂°似流年/ 2023年06月22日 03:25/ 0 赞/ 130 阅读

相关树上倍增求链上最大值或最小值

倍增求链上点最大值 inline int LCA(int x,int y) { int maxn=max(w[x],w[y]); if (deep[x]>deep[y

蔚落/ 2023年06月01日 15:00/ 0 赞/ 72 阅读

相关 Hadoop_MapReduce_求最大值和最小值

Hadoop\_MapReduce\_求最大值和最小值 1. 原始数据：D:\\data\\nums.txt 需求：找出最大和最小的数字 3

拼搏现实的明天。/ 2023年03月13日 07:00/ 0 赞/ 115 阅读

相关求数组最大值最小值

include <iostream> include <algorithm> using namespace std; in

古城微笑少年丶/ 2022年09月12日 01:44/ 0 赞/ 420 阅读

相关分治法求最大最小值

include<iostream> include<stdio.h> using namespace std; int max(int

系统管理员/ 2022年07月11日 12:22/ 0 赞/ 326 阅读

相关 java 一维数组求最大值最小值

package 第二次作业; //java包 import java.util.S

悠悠/ 2022年06月07日 03:54/ 0 赞/ 506 阅读

相关 C++求矩阵最大值和最小值

include <iostream> using namespace std; float max(float a[],int n)

￡神魔★判官ぃ/ 2022年05月15日 03:11/ 0 赞/ 512 阅读