Submission #43178109

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
const int N=300010,M=2*N;
int n,h[N],e[M],ne[M],d[N],w[M],idx,k;
typedef long long ll;
const ll inf=1e18;
ll f[2][N],a[N];
void add(int a,int b,int c){
    w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int x,int fa){
    ll &sum=f[0][x];
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        dfs(j,x);
    }
    int cur=0;
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        ll tmp=f[1][j]+w[i]-f[0][j];
        if(j==fa)continue;
        sum+=f[0][j];
        if(tmp>0)a[++cur]=tmp;
    }
    f[1][x]=d[x]?sum:-inf;
    if(!d[x])return;
    k=cur;
    if(d[x]-1<cur)k=d[x]-1;
    if(k&&k!=cur)nth_element(a+1,a+(cur-k+1),a+1+cur);
    Le(i, cur-k+1, cur)f[1][x]+=a[i];
    sum=f[1][x];
    int maxn=0;
    E(i, cur-k)
        if(a[i]>maxn)maxn=a[i];
    sum+=maxn;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    #endif
    // Insert Code Here
    scanf("%d",&n);
    memset(h,-1,n*4+4);
    E(i, n)scanf("%d",d+i);
    E(i, n-1){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a, b, c);
        add(b,a, c);
    }
    dfs(1,-1);
    printf("%lld",f[0][1]);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:56:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   56 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
./Main.cpp:58:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   58 |     E(i, n)scanf("%d",d+i);
      |            ~~~~~^~~~~~~~~~
./Main.cpp:61:14: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   61 |         scanf("%d%d%d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Judge Result