树形Dp WA 50pts求调

114514xxx @ 2024-10-28 15:43:43

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+25;
struct Edge{
    int to,next;
}edge[N];
struct obj{
    int v,w;
}a[N];
int head[N],cnt;
inline void add(int x,int y){
    edge[++cnt].to=y;
    edge[cnt].next=head[x];
    head[x]=cnt;
}
int W,m;
int dp[300][N];
inline void dfs(int u,int V,int fa){
    if(V<0)return;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa)return;
        for(int k=W-a[i].w;k>=0;--k)
            dp[v][k]=dp[u][k]+a[v].v;
        dfs(v,V-a[v].w,u);
        for(int k=W;k>=a[v].w;--k)
            dp[u][k]=max(dp[u][k],dp[v][k-a[v].w]);
    }
}
signed main(){
    cin>>W>>m;
    int v,p,q;
    for(int i=1;i<=m;i++){
        cin>>v>>p>>q;
        a[i].v=v*p;
        a[i].w=v;
        add(i,q);
        add(q,i);
    }
    dfs(0,W,-1);
    int ans=0;
    cout<<dp[0][W];
}

by 114514xxx @ 2024-10-28 16:05:29

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+25;
struct Edge{
    int to,next;
}edge[N];
struct obj{
    int v,w;
}a[N];
int head[N],cnt;
inline void add(int x,int y){
    edge[++cnt].to=y;
    edge[cnt].next=head[x];
    head[x]=cnt;
}
int W,m;
int dp[300][N];
inline void dfs(int u,int V,int fa){
    if(V<=0)return;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa)return;
        for(int k=W+1;k>=a[i].w;k--)
            dp[v][k]=dp[u][k]+a[v].v;
        dfs(v,V-a[v].w,u);
        for(int k=W+1;k>=a[v].w;k--)
            dp[u][k]=max(dp[u][k],dp[v][k-a[v].w]);
    }
}
signed main(){
    cin>>W>>m;
    int v,p,q;
    for(int i=1;i<=m;i++){
        cin>>v>>p>>q;
        a[i].v=v*p;
        a[i].w=v;
        add(i,q);
        add(q,i);
    }
    dfs(0,W,-1);
    int ans=0;
        for(int j=0;j<=W;j++)
            ans=max(ans,dp[0][j]);
    cout<<ans;
}

现在 subtask#1 没过