虚树 · ooliver

P4103 [HEOI2014] 大工程先建虚树，对于最大值和最小值是很好维护的，对于总和，我们用一个标记记录当前节点作为 lca 的贡献次数，递归到子节点后在加上贡献次数。 C++ #include using namespace std; #define int long long #define lc p t[N],g[N]; bool cmp(int x,int y){return dfn[x]siz[son[u]]) son[u]=v; } } void dfs2(int u,int tp){ top[u]=tp,dfn[u]=++idx; if(!son[u]) return; dfs2(son[u],tp); for(int v:g[u]){ if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } } int lca(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]dep[y]?y:x; } void build(){ int len=0; sort(a+1,a+1+k,cmp); for(int i=1;i>n; for(int i=1;i>u>>v; g[u].push_back(v); g[v].push_back(u); } mn[i]=1e18,mx[i]=-1e18; } dfs1(1,0),dfs2(1,1); cin>>m; while(m--){ ans1=0,ans2=1e18,ans3=-1e18; cin>>k; for(int i=1;i>a[i],tag[a[i]]=1; build(); dfs3(node[1]),dfs4(node[1],0); cout `#include using namespace std; #define int long long #define lc p #define rc p const int N=1e6+5; int n,m,k,idx; int ans1,ans2,ans3; int a[N],node[N],tag[N],sum[N],mn[N],mx[N]; int fa[N],son[N],dep[N],top[N],siz[N],dfn[N]; vector t[N],g[N]; bool cmp(int x,int y){return dfn[x]dfn[y];} void dfs1(int u,int f){ fa[u]=f,siz[u]=1,dep[u]=dep[f]+1; for(int v:g[u]){ if(v==f) continue; dfs1(v,u); siz[u]+=siz[v]; if(siz[v]>siz[son[u]]) son[u]=v; } } void dfs2(int u,int tp){ top[u]=tp,dfn[u]=++idx; if(!son[u]) return; dfs2(son[u],tp); for(int v:g[u]){ if(v==fa[u]||v==son[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]?y:x; } void build(){ int len=0; sort(a+1,a+1+k,cmp); for(int i=1;ik;i++){ node[++len]=a[i]; if(ik){ int f=lca(a[i],a[i+1]); node[++len]=f; } } sort(node+1,node+1+len,cmp); len=unique(node+1,node+1+len)-node-1; for(int i=1;ilen;i++){ int f=lca(node[i],node[i+1]); t[f].push_back(node[i+1]); } } void dfs3(int u){ sum[u]=tag[u]; for(int v:t[u]){ dfs3(v); sum[u]+=sum[v]; } } void dfs4(int u,int k1){ if(tag[u]) ans1+=dep[u]*k1,mn[u]=mx[u]=dep[u]; for(int v:t[u]){ ans1-=sum[v]*(sum[u]-sum[v])*dep[u]; dfs4(v,k1+(sum[u]-sum[v])); ans2=min(ans2,mn[v]+mn[u]-2*dep[u]),ans3=max(ans3,mx[v]+mx[u]-2*dep[u]); mn[u]=min(mn[u],mn[v]),mx[u]=max(mx[u],mx[v]); mn[v]=1e18,mx[v]=-1e18; } t[u].clear(); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; for(int i=1;in;i++){ if(in){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } mn[i]=1e18,mx[i]=-1e18; } dfs1(1,0),dfs2(1,1); cin>>m; while(m--){ ans1=0,ans2=1e18,ans3=-1e18; cin>>k; for(int i=1;ik;i++) cin>>a[i],tag[a[i]]=1; build(); dfs3(node[1]),dfs4(node[1],0); coutans1" "ans2" "ans3"\n"; for(int i=1;ik;i++) tag[a[i]]=0; mn[node[1]]=1e18,mx[node[1]]=-1e18; } return 0; }` P2495 【模板】虚树 / [SDOI2011] 消耗战这个是虚树模板。建虚树后直接 dp 即可，分两种情况：切断当前节点与根节点路径的最小边切断所有子树节点与根节点路径的最小边代码： C++ #include using namespace std; #define int long long const int N=5e5+5; int n,m,k,idx; int a[N],node[N],tag[N]; int mn[N],dp[N]; int fa[N],son[N],dep[N],top[N],siz[N],dfn[N]; struct edge{ int v,w; }; vector g[N]; vector t[N]; bool cmp(int x,int y){return dfn[x]siz[son[u]]) son[u]=v; } } void dfs2(int u,int tp){ top[u]=tp,dfn[u]=++idx; if(!son[u]) return; dfs2(son[u],tp); for(edge x:g[u]){ int v=x.v,w=x.w; if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } } int lca(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]dep[y]?y:x; } void build(){ int len=0; sort(a+1,a+1+k,cmp); for(int i=1;i>n; for(int i=1;i>u>>v>>w; g[u].push_back({v,w}); g[v].push_back({u,w}); } mn[1]=LONG_LONG_MAX; dfs1(1,0),dfs2(1,1); cin>>m; while(m--){ cin>>k; for(int i=1;i>a[i],tag[a[i]]=1; build(); dfs(node[1]); cout `#include using namespace std; #define int long long const int N=5e5+5; int n,m,k,idx; int a[N],node[N],tag[N]; int mn[N],dp[N]; int fa[N],son[N],dep[N],top[N],siz[N],dfn[N]; struct edge{ int v,w; }; vectoredge> g[N]; vector t[N]; bool cmp(int x,int y){return dfn[x]dfn[y];} void dfs1(int u,int f){ fa[u]=f,siz[u]=1,dep[u]=dep[f]+1; for(edge x:g[u]){ int v=x.v,w=x.w; if(v==f) continue; mn[v]=min(mn[u],w); dfs1(v,u); siz[u]+=siz[v]; if(siz[v]>siz[son[u]]) son[u]=v; } } void dfs2(int u,int tp){ top[u]=tp,dfn[u]=++idx; if(!son[u]) return; dfs2(son[u],tp); for(edge x:g[u]){ int v=x.v,w=x.w; if(v==fa[u]||v==son[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]?y:x; } void build(){ int len=0; sort(a+1,a+1+k,cmp); for(int i=1;ik;i++){ node[++len]=a[i]; if(ik){ int f=lca(a[i],a[i+1]); node[++len]=f; } } sort(node+1,node+1+len,cmp); len=unique(node+1,node+1+len)-node-1; for(int i=1;ilen;i++){ int f=lca(node[i],node[i+1]); t[f].push_back(node[i+1]); } } void dfs(int u){ int sum=0; for(int v:t[u]){ dfs(v); sum+=dp[v],dp[v]=0; } if(tag[u]) dp[u]=mn[u]; else dp[u]=min(mn[u],sum); t[u].clear(); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; for(int i=1;in;i++){ int u,v,w; cin>>u>>v>>w; g[u].push_back({v,w}); g[v].push_back({u,w}); } mn[1]=LONG_LONG_MAX; dfs1(1,0),dfs2(1,1); cin>>m; while(m--){ cin>>k; for(int i=1;ik;i++) cin>>a[i],tag[a[i]]=1; build(); dfs(node[1]); coutdp[node[1]]"\n"; for(int i=1;ik;i++) tag[a[i]]=0; } return 0; }` P3233 [HNOI2014] 世界树先建虚树，现在分两种情况：虚树内的节点：做两次 dfs，上下遍历更新两次即可。不在虚树上的节点：在第二次 dfs 的边的枚举中单独计算，从子节点倍增跳到父节点，找到边上的临界点即可。代码： C++ #include using namespace std; #define int long long #define lc p t[N],g[N]; bool cmp(int x,int y){return dfn[x]=0;i--) if(d[fa[u][i]]>=d[v]) u=fa[u][i]; if(u==v) return u; for(int i=20;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } void build(){ int len=1; node[1]=1,sort(a+1,a+1+k,cmp); for(int i=1;i=0;i--) if(d[fa[x][i]]>d[u]) x=fa[x][i]; ans[p[u]]-=siz[x]; for(int i=20;i>=0;i--){ int d1=d[v]-d[fa[y][i]]+dis[v],d2=d[fa[y][i]]-d[u]+dis[u]; if(d[fa[y][i]]>d[u]&&(d1>n; for(int i=1;i>u>>v; g[u].push_back(v); g[v].push_back(u); } dfs(1,0); cin>>m; while(m--){ cin>>k; for(int i=1;i>a[i],b[i]=a[i],tag[a[i]]=1; build(); dfs1(1),dfs2(1); for(int i=1;i `#include using namespace std; #define int long long #define lc p #define rc p const int N=3e5+5; int n,m,k,idx; int a[N],b[N],node[N],tag[N]; int dfn[N],siz[N],fa[N][25],d[N]; int dis[N],p[N],ans[N]; vector t[N],g[N]; bool cmp(int x,int y){return dfn[x]dfn[y];} void dfs(int u,int f){ siz[u]=1,fa[u][0]=f,d[u]=d[f]+1,dfn[u]=++idx; for(int i=1;i18;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int v:g[u]){ if(v==f) continue; dfs(v,u); siz[u]+=siz[v]; } } int lca(int u,int v){ if(d[u]d[v]) swap(u,v); for(int i=20;i>=0;i--) if(d[fa[u][i]]>=d[v]) u=fa[u][i]; if(u==v) return u; for(int i=20;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } void build(){ int len=1; node[1]=1,sort(a+1,a+1+k,cmp); for(int i=1;ik;i++){ node[++len]=a[i]; if(ik){ int f=lca(a[i],a[i+1]); node[++len]=f; } } sort(node+1,node+1+len,cmp); len=unique(node+1,node+1+len)-node-1; for(int i=1;ilen;i++){ int f=lca(node[i],node[i+1]); t[f].push_back(node[i+1]); } } void get(int u,int v){ int x=v,y=v; for(int i=20;i>=0;i--) if(d[fa[x][i]]>d[u]) x=fa[x][i]; ans[p[u]]-=siz[x]; for(int i=20;i>=0;i--){ int d1=d[v]-d[fa[y][i]]+dis[v],d2=d[fa[y][i]]-d[u]+dis[u]; if(d[fa[y][i]]>d[u]&&(d1d2||(d1==d2&&p[v]p[u]))) y=fa[y][i]; } ans[p[u]]+=siz[x]-siz[y],ans[p[v]]+=siz[y]-siz[v]; } void dfs1(int u){ dis[u]=1e18; for(int v:t[u]){ dfs1(v); if(d[v]-d[u]+dis[v]dis[u]) dis[u]=d[v]-d[u]+dis[v],p[u]=p[v]; else if(d[v]-d[u]+dis[v]==dis[u]) p[u]=min(p[v],p[u]); } if(tag[u]) dis[u]=0,p[u]=u; } void dfs2(int u){ for(int v:t[u]){ if(d[v]-d[u]+dis[u]dis[v]) dis[v]=d[v]-d[u]+dis[u],p[v]=p[u]; else if(d[v]-d[u]+dis[u]==dis[v]) p[v]=min(p[v],p[u]); get(u,v); dfs2(v); } ans[p[u]]+=siz[u]; tag[u]=0,t[u].clear(); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; for(int i=1;in;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } dfs(1,0); cin>>m; while(m--){ cin>>k; for(int i=1;ik;i++) cin>>a[i],b[i]=a[i],tag[a[i]]=1; build(); dfs1(1),dfs2(1); for(int i=1;ik;i++) coutans[b[i]]" ",tag[b[i]]=0,ans[b[i]]=0; cout"\n"; } return 0; }` P3320 [SDOI2015] 寻宝游戏有一个结论：虚树的边权和的两倍等于把所有关键点按 dfn 序排序并对相邻两个节…