当前位置: 首页 > news >正文

虚树学习笔记

好久没更学习笔记了。

算法简介

通常情况下,如果是对树上单点的询问,我们是用不到树上的所有点的。

换句话说,如果我们树上能用到的节点非常少,那我们就可以避免遍历整棵树,从而降低复杂度。

下面用一个题说。

消耗战/【模板】虚树

先想朴素的 dp 做法:设 \(f_i\) 表示 \(i\) 不与子树中任意一个关键点连接的最小代价。

枚举 \(i\) 的子树 \(v\),则有转移方程:

  • \(v\) 不是关键点 \(f_i=f_i+\min(f_v,w(i,v))\)

  • \(v\) 是关键点 \(f_i=f_i+w(i,v)\)

非常简单对吧。

但是这个玩意是 \(O(nq)\) 的,根本跑不动。

但是 \(\sum k\) 比较小,所以我们考虑如果每次只遍历 \(k\) 个点,复杂度就可以控制住了。

然后再观察转移式子,发现 \(min(i,v)\) 这一项实际上是链上最小值,这个信息是轻松维护的,我们考虑建出虚树,对虚树 dp。

然后我们就可以考虑建虚树了。

一些定义

虚树上的节点我们称为关键点,关键点包含询问的节点和两两之间的 LCA。

方法一:两遍排序 LCA

先将关键点按 DFS 序排序后,两两求 LCA。

对选出来的点集去重后按 DFS 序排序,再两两求 LCA,并连边。

方法二:单调栈构建虚树

我们用单调栈维护虚树上的一条链,栈中的点在虚树上是相邻的,而且栈中自底向上 DFS 序递增。

然后我们就对不同的情况分讨即可。贴一个代码。

sort(h+1,h+1+k,cmp);
t=0;sta[++t]=h[1];
for(int i=2;i<=k;i++){int now=h[i],lca=LCA(now,sta[t]);while(1){if(dep[lca]>=dep[sta[t-1]]){if(lca!=sta[t]){M[lca].push_back(sta[t]);if(lca!=sta[t-1]) sta[t]=lca;else t--;}break;}else{M[sta[t-1]].push_back(sta[t]);t--;}}sta[++t]=now;
}
while(--t) M[sta[t]].push_back(sta[t+1]);

然后对着新生成的树正常跑 dp 即可。

撤销的时候按 DFS 序撤销,不要 memest 式清空,不然复杂度就退化了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int N = 2.5e5+10;
int dfn[N],dfx,siz[N],top[N],hson[N],fa[N],dep[N];
struct Edge{int v;ll w;
};
ll minv[N];
int n,m,k,h[N];
bool q[N];
vector<Edge> G[N];
vector<int> M[N];
void dfs1(int u,int f){fa[u]=f;siz[u]=1;dep[u]=dep[f]+1;for(auto to:G[u]){int v=to.v;if(v==f) continue;minv[v]=min(minv[u],to.w);dfs1(v,u);siz[u]+=siz[v];if(siz[v]>siz[hson[u]]) hson[u]=v;}
}
void dfs2(int u,int tp){top[u]=tp;dfn[u]=++dfx;if(!hson[u]) return ;dfs2(hson[u],tp);for(auto to:G[u]){int v=to.v;if(v==fa[u] || v==hson[u]) continue;dfs2(v,v);}
}
int LCA(int x,int y){while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);x=fa[top[x]];}return dep[x]<dep[y] ? x : y;
}
bool cmp(int x,int y){return dfn[x]<dfn[y];
}
int sta[N],t;
ll dfs3(int u){ll sum=0,tmp;for(int v:M[u]){sum+=dfs3(v);}if(q[u])tmp=minv[u];else tmp=min(sum,minv[u]);q[u]=false;M[u].clear();return tmp;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);minv[1]=1e18;cin>>n;for(int i=1,u,v,w;i<n;i++){cin>>u>>v>>w;G[u].push_back({v,w});G[v].push_back({u,w});}dfs1(1,0);dfs2(1,1);cin>>m;while(m--){cin>>k;for(int i=1;i<=k;i++){cin>>h[i];q[h[i]]=1;}sort(h+1,h+1+k,cmp);t=0;sta[++t]=h[1];for(int i=2;i<=k;i++){int now=h[i],lca=LCA(now,sta[t]);while(1){if(dep[lca]>=dep[sta[t-1]]){if(lca!=sta[t]){M[lca].push_back(sta[t]);if(lca!=sta[t-1]) sta[t]=lca;else t--;}break;}else{M[sta[t-1]].push_back(sta[t]);t--;}}sta[++t]=now;}while(--t) M[sta[t]].push_back(sta[t+1]);cout << dfs3(sta[1]) << '\n';}return 0;
}
http://www.hskmm.com/?act=detail&tid=28680

相关文章:

  • 市场营销:
  • Python3开发敏感词过滤程序底层逻辑记录
  • OUC《软件工程原理与实践》- 实验2:深度学习基础 - OUC
  • 类型转化
  • 【IEEE出版】第五届电子信息工程与计算机技术国际学术会议(EIECT 2025)
  • 【AP出版】第七届文学、艺术与人文发展国际学术会议(ICLAHD 2025)
  • 事件驱动重塑 AI 数据链路:阿里云 EventBridge 发布 AI ETL 新范式
  • 我把Excel变成了像素画板!用Python实现图片到单元格的映射
  • 如何通过内核版本检查判断FreeBSD是否需要重启
  • 2025 年山东染井吉野樱 / 高杆染井吉野樱花 / 染井吉野樱花小苗厂家推荐:绿影园林的培育技术与全规格供应解析
  • C#中关于InvokeRequired 属性 与Invoke方法
  • 云存储成本自动优化技术解析
  • MZOI 20251011【CSP-】模拟 T2 序列区间
  • SAP 中CONCATENATE 空格的时候,空格不生效
  • Java的各类定时任务实现
  • 03:运算符
  • JavaScript内存泄露原因及解决方案
  • 数据类型扩展
  • 2025 年最新金蝶云服务商推荐榜单:聚焦铂金伙伴技术实力与万级客户口碑,助力企业数字化转型精准选型上海金蝶云服务商推荐
  • OIFHA251011 比赛总结
  • P2051 [AHOI2009] 中国象棋 个人题解
  • 一种智能调度分布式路径计算解决方案
  • 使用 C++ 和 minizip 实现 ZIP 压缩解压工具
  • 一看就懂,Oracle认证体系中的OCP中级认证
  • 2025 年试验机生产厂家最新推荐榜单:聚焦优质企业,助力精准选购高低温等各类试验设备弹簧拉压/弹簧疲劳/高频弹簧疲劳/U型弹簧专用试验机厂家推荐
  • IIS/如何查看IIS上部署网站的实时连接数
  • 拼叨叨砍价系统:实体店低成本引流的营销利器
  • 2025 自动门生产厂家最新推荐榜:权威筛选优质品牌,含选购指南与实力厂家深度解析
  • 医德出诊排班挂号管理系统:医院高效运营与便民服务的智能解决方案
  • 一佳教育培训课程系统小程序:一站式教育数字化解决方案