正題

題目鏈接:https://www.luogu.com.cn/problem/P2495

---

題目大意

$n$個點的一棵樹，$m$次給出一些點，要求割掉最小權值的邊使得這些點不和$1$號點聯通。

---

解題思路

根據這些給出的點構造一棵虛樹，然后直接$dp$求解即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=3e5+10,T=20,inf=1e18; struct node{ll to,next,w; }a[N*2]; ll n,m,tot,cnt,st,k,dep[N],dfn[N],ls[N],p[N]; ll f[N][T+1],g[N][T+1],pos[N],s[N],dp[N][2]; bool cmp(ll x,ll y) {return dfn[x]<dfn[y];} void addl(ll x,ll y,ll w){if(dep[x]>dep[y])swap(x,y);a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;return; } void dfs(ll x,ll fa){dfn[x]=++cnt;dep[x]=dep[fa]+1;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;f[y][0]=x;g[y][0]=a[i].w;dfs(y,x);}return; } ll LCA(ll x,ll y){if(dep[x]>dep[y])swap(x,y);for(ll i=T;i>=0;i--)if(dep[f[y][i]]>=dep[x])y=f[y][i];if(x==y)return x;for(ll i=T;i>=0;i--)if(f[y][i]!=f[x][i])x=f[x][i],y=f[y][i];return f[x][0]; } ll Dis(ll x,ll y){ll ans=inf;if(dep[x]>dep[y])swap(x,y);for(ll i=T;i>=0;i--)if(dep[f[y][i]]>=dep[x])ans=min(ans,g[y][i]),y=f[y][i];return ans; } void ins(ll x){if(!st){s[++st]=x;return;}ll lca=LCA(x,s[st]);while(st>1&&dep[s[st-1]]>dep[lca])addl(s[st-1],s[st],Dis(s[st-1],s[st])),st--;if(dep[s[st]]>dep[lca])addl(lca,s[st],Dis(lca,s[st])),st--;if((!st)||(lca!=s[st]))s[++st]=lca;s[++st]=x;return; } void solve(ll x){if(pos[x])dp[x][1]=0,dp[x][0]=inf;else dp[x][0]=0,dp[x][1]=0;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;solve(y);dp[x][0]+=min(dp[y][0],dp[y][1]+a[i].w);dp[x][1]=min(dp[x][0]+dp[y][1],min(dp[x][1]+dp[y][0],dp[x][1]+dp[y][1]));}ls[x]=pos[x]=0;return; } int main() {scanf("%lld",&n);for(ll i=1;i<n;i++){ll x,y,w;scanf("%lld%lld%lld",&x,&y,&w);addl(x,y,w);addl(y,x,w);}memset(g,0x3f,sizeof(g));dfs(1,0);for(ll j=1;j<=T;j++)for(ll i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1],g[i][j]=min(g[i][j-1],g[f[i][j-1]][j-1]);memset(ls,0,sizeof(ls));scanf("%lld",&m);while(m--){scanf("%lld",&k);st=tot=0;for(ll i=1;i<=k;i++){scanf("%lld",&p[i]);pos[p[i]]=1;}sort(p+1,p+1+k,cmp);s[++st]=1;for(ll i=1;i<=k;i++)ins(p[i]);while(st>1)addl(s[st-1],s[st],Dis(s[st-1],s[st])),st--;solve(1);printf("%lld\n",dp[1][0]);}return 0; }

總結

以上是生活随笔為你收集整理的P2495-[SDOI2011]消耗战【虚树,dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。