最终决定重新打一遍这题 然后被儿子覆盖的这个情况还是重新看一遍以前的代码才捋清楚QAQ
每个点有三种状态 自己覆盖自己 被父亲覆盖 被儿子覆盖
然后要注意被儿子覆盖时的转移 最后如果都是儿子被孙子覆盖的花费更少的话 得选一个儿子自己覆盖自己花费最少的来覆盖
最后输出根节点中自己覆盖自己和被儿子覆盖中较小的一个
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 #include<cmath> 6 #include<stack> 7 #include<algorithm> 8 using namespace std; 9 #define ll long long 10 #define rg register 11 const int N=1500+5,inf=0x3f3f3f3f; 12 int n,a[N],ns,s,f[N][3]; 13 template <class t>void rd(t &x) 14 { 15 x=0;int w=0;char ch=0; 16 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 17 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 18 x=w?-x:x; 19 } 20 21 int head[N],tot=0; 22 struct edge{int v,nxt,w;}e[N<<1]; 23 void add(int u,int v) 24 { 25 e[++tot].v=v,e[tot].nxt=head[u],head[u]=tot; 26 } 27 28 void dp(int u,int fa) 29 { 30 f[u][0]=a[u],f[u][1]=f[u][2]=0; 31 bool yes=0;int minc=inf; 32 for(int i=head[u];i;i=e[i].nxt) 33 { 34 int v=e[i].v; 35 if(v==fa) continue; 36 dp(v,u); 37 f[u][0]+=min(f[v][1],min(f[v][0],f[v][2]));//自己覆盖自己 38 f[u][1]+=min(f[v][0],f[v][2]);//被父亲覆盖 39 f[u][2]+=min(f[v][0],f[v][2]) ;//被儿子覆盖 40 if(f[v][0]<=f[v][2]) yes=1; 41 else minc=min(minc,f[v][0]-f[v][2]); 42 } 43 if(!yes) f[u][2]+=minc; 44 } 45 46 int main() 47 { 48 //freopen("in.txt","r",stdin); 49 //freopen("nocows.out","w",stdout); 50 rd(n); 51 for(rg int i=1;i<=n;++i) 52 { 53 rd(i),rd(a[i]),rd(ns); 54 for(rg int j=1;j<=ns;++j) rd(s),add(i,s),add(s,i); 55 } 56 dp(1,0); 57 printf("%d",min(f[1][0],f[1][2])); 58 return 0; 59 }