好久没更学习笔记了。
算法简介
通常情况下,如果是对树上单点的询问,我们是用不到树上的所有点的。
换句话说,如果我们树上能用到的节点非常少,那我们就可以避免遍历整棵树,从而降低复杂度。
下面用一个题说。
消耗战/【模板】虚树
先想朴素的 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;
}