本文主要是介绍(Luogu) P2495 [SDOI2011]消耗战 （虚树+动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
虚树入门
题目传送门
虚树的主要思想就是对于一棵树，仅仅保留有用的点，重新构建一棵树。
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=250005;
template <typename _Tp> il void read(_Tp&x) {char ch;bool flag=0;x=0;while(ch=getchar(),!isdigit(ch)) if(ch=='-')flag=1;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();if(flag) x=-x;
}
//il int Add(int &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(int &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
struct node{int to,w;
};
vector<node> G[N];
int n,m,a[N],dfn[N],topf[N],siz[N],son[N];
int s[N],top,deep[N],fa[N],ID=0;
ll mn[N];
void dfs1(int x, int f) {siz[x]=1; fa[x]=f;for(auto tp:G[x]) {int to=tp.to,w=tp.w;if(to==f) continue;deep[to]=deep[x]+1;mn[to]=min(mn[x],(ll)w);dfs1(to,x);siz[x]+=siz[to];if(siz[to]>siz[son[x]]) son[x] = to;}
}
void dfs2(int x, int topfa) {topf[x]=topfa;dfn[x]=++ID;if(!son[x]) return ;dfs2(son[x], topfa);for(auto tp:G[x]) if(!topf[tp.to]) dfs2(tp.to, tp.to);
}
int Lca(int x, int y) {while(topf[x]!=topf[y]) {if(deep[topf[x]]<deep[topf[y]]) swap(x, y);x = fa[topf[x]];}if(deep[x]<deep[y]) swap(x, y);return y;
}
vector<int> mp[N];
il void add_edge(int u,int v){mp[u].pb(v);
}
il void add(int x){if(top==1){s[++top]=x;return;}int lca=Lca(x,s[top]);if(lca==s[top]) return;while(top>1 && dfn[s[top-1]]>=dfn[lca]) add_edge(s[top-1],s[top]),top--;if(lca!=s[top]) add_edge(lca,s[top]),s[top] = lca;s[++top]=x;
}
il ll solve(int x) {if(mp[x].size()==0) return mn[x];ll sum=0;for(auto to:mp[x]) sum+=solve(to);mp[x].clear();return min(sum,(ll)mn[x]);
}
il bool cmp(int x,int y){return dfn[x]<dfn[y];
}
int main(){
// std::ios::sync_with_stdio(0);cin.tie(0);mn[1]=1e18;read(n);for(int i=1,u,v,w;i<=n-1;++i){read(u),read(v),read(w);G[u].pb({v,w});G[v].pb({u,w}); }deep[1]=1;dfs1(1,0);dfs2(1,1);read(m);int k;while(m--){read(k);for(int i=1;i<=k;++i) read(a[i]);sort(a+1,a+k+1,cmp);top=1;s[top]=1;for(int i=1;i<=k;++i) add(a[i]);while(top>0) add_edge(s[top-1],s[top]),top--;printf("%lld\n",solve(1));}return 0;
}
这篇关于(Luogu) P2495 [SDOI2011]消耗战 （虚树+动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
