题目保证了给先出结点的一定时后面结点的兄弟或者祖先,所以我们能可以直接选择递推 特判根结点,他的点权就是s[1] 对结点i,如果他的s[i]=-1 要使所有点权和最小,那么s[i]=min(s[j]) j是i的儿子结点 ans[i] = s[k]-s[i] k是i的父亲结点 如果ans[i]<0 说明无解 如果s[i]!=-1 那么 ans[i]=s[k]-s[i] 判断ans[i]是否小于0 k和j在输入的时候就能处理好,然后递推就完事了
#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<iostream> #include<vector> #include<map> #include<set> #include<stack> #include<queue> #include<stdlib.h> #include<algorithm> #include<time.h> #include<unordered_map> #define bug1(g) cout<<"test: "<<g<<endl #define bug2(g,i) cout<<"test: "<<g<<" "<<i<<endl #define bug3(g,i,k) cout<<"test: "<<g<<" "<<i<<" "<<k<<endl #define bug4(a,g,i,k) cout<<"test: "<<a<<" "<<g<<" "<<i<<" "<<k<<endl using namespace std; typedef long long ll; int n; vector<int>a[100005]; int s[100005],h[100005],la[100005]; int ans[100005]; int main() { ios::sync_with_stdio(0); cin>>n; int x; for(int i =2;i<=n;i++) { cin>>x; a[x].push_back(i); la[i]=x; } for(int i =1;i<=n;i++) cin>>s[i]; int flag=0; ll sum=0; for(int i =1;i<=n;i++) { if(i==1) ans[i]=s[i]; else { if(s[i]==-1) { s[i]=1e9+5; for(int j=0;j<a[i].size();j++) { s[i]=min(s[a[i][j]],s[i]); } ans[i]=s[i]-s[la[i]]; if(ans[i]<0) {flag=1;} if(a[i].size()==0 )ans[i]=0; } else { ans[i]=s[i]-s[la[i]]; if(ans[i]<0) flag=1; } } sum+=ans[i]; if(flag) break; } if(flag) cout<<-1<<endl; else cout<<sum<<endl; return 0; }