没注意放置时还有权值还行
#include<bits/stdc++.h> using namespace std; int n,val[150000],m,ne,a,b,head[150000],f[150000][3]; struct node{int nxt,to;}eg[150000]; void adde(int u,int v){eg[++ne].nxt=head[u];eg[ne].to=v;head[u]=ne;} void dfs(int u,int fa) { int sum=0; f[u][0]=val[u]; for(int i=head[u];i;i=eg[i].nxt) { int v=eg[i].to; if(v==fa)continue; dfs(v,u); f[u][0]+=min(min(f[v][1],f[v][0]),f[v][2]); sum+=(min(f[v][2],f[v][0])); } f[u][1]=sum;f[u][2]=0x3f3f3f3f; for(int i=head[u];i;i=eg[i].nxt) { int v=eg[i].to; if(v==fa)continue; f[u][2]=min(f[u][2],sum-min(f[v][2],f[v][0])+f[v][0]); } } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a; cin>>val[a]>>m; while(m--) { cin>>b; adde(a,b);adde(b,a); } } dfs(1,0); cout<<min(f[1][0],f[1][2]); }