Submission #1165784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165784		Ludissey	Chase (CEOI17_chase)	C++20	20 / 100	579 ms	496356 KiB

chase

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

int v;
vector<int> p;
vector<int> np;
vector<vector<int>> neigh;
vector<vector<int>> dpu;
vector<vector<int>> dpd;
int ans=0;

void dfs(int x, int _p){
    for (auto u : neigh[x])
    {
        if(u==_p) continue;
        dfs(u,x);
        for (int j = 0; j <= v; j++)
        {
            dpu[x][j]=max(dpu[u][j], dpu[x][j]);
            if(j>0) dpu[x][j]=max(dpu[x][j],dpu[u][j-1]+np[x]-p[u]);
            dpd[x][j]=max(dpd[u][j],dpd[x][j]);
            if(_p>=0&&j>0) dpd[x][j]=max(dpd[u][j-1]+np[x]-p[_p],dpd[x][j]);
        }
    }
    for (int j = 1; j <= v; j++) dpu[x][j]=max(np[x],dpu[x][j]);
    for (int j = 1; j <= v; j++) {
        if(_p>=0) dpd[x][j]=max(np[x]-p[_p],dpd[x][j]);
        else dpd[x][j]=max(np[x],dpd[x][j]);
    }
}

void calc(int x, int _p){
    vector<pair<pair<int,int>,pair<int,int>>> up(v+1, {{-1,-1},{-1,-1}});
    vector<pair<pair<int,int>,pair<int,int>>> up2(v+1, {{-1,-1},{-1,-1}});
    for (auto u : neigh[x])
    {
        if(u==_p) continue;
        calc(u,x);
        for (int j = 0; j <= v; j++)
        {
            if(dpu[u][j]>up[j].first.first) up[j]={{dpu[u][j],u},up[j].first};
            else if(dpu[u][j]>up[j].second.first) up[j].second={dpu[u][j],u};

            if(dpu[u][j]-p[u]>up2[j].first.first) up2[j]={{dpu[u][j]-p[u],u},up2[j].first};
            else if(dpu[u][j]-p[u]>up2[j].second.first) up2[j].second={dpu[u][j]-p[u],u};
        }
    }
    for (auto u : neigh[x])
    {
        if(u==_p) continue;
        for (int j = 0; j <= v; j++)
        {
            int x1=up[v-j].first.first;
            if(up[v-j].first.second==u) x1=up[v-j].second.first;
            ans=max(ans,x1+dpd[u][j]);
            if(j==v) continue;
            x1=up2[v-j-1].first.first;
            if(up2[v-j-1].first.second==u) {
                if(up2[v-j-1].second.second==-1) {x1=-1e9; continue; }
                x1=up2[v-j-1].second.first; 
            }
            ans=max(ans,x1+dpd[u][j]+np[x]);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n >> v;
    p.resize(n); neigh.resize(n); np.resize(n,0);
    dpu.resize(n,vector<int>(v+1, 0));
    dpd.resize(n,vector<int>(v+1, 0));
    for (int i = 0; i < n; i++) cin >> p[i];
    for (int i = 0; i < n-1; i++)
    {
        int a,b; cin >> a >> b;
        neigh[a-1].push_back(b-1);
        neigh[b-1].push_back(a-1);
        np[a-1]+=p[b-1];
        np[b-1]+=p[a-1];
    }
    dfs(0,-1);  
    calc(0,-1);
    cout << ans << "\n";  
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30