Submission #146249

#	Time	Username	Problem	Language	Result	Execution time	Memory
146249		lyc	Chase (CEOI17_chase)	C++14	100 / 100	808 ms	344056 KiB

chase

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 1e5+5;
const int MAXV = 105;

int N, V;
int P[MAXN];
vector<int> al[MAXN]; int pa[MAXN];
ll f[MAXN][MAXV], g[MAXN][MAXV], h[MAXN][MAXV][2];
ll surr[MAXN];

void down(int u, int p) {
    pa[u] = p;
    surr[u] = 0;
    for (auto v : al[u]) if (v != p) {
        down(v,u);
        surr[u] += P[v];
    }

    f[u][0] = 0;
    FOR(x,1,V) {
        for (auto v : al[u]) if (v != p) {
            f[u][x] = max({ f[u][x], f[v][x], f[v][x-1]+surr[u] });
        }
    }
    
}

void up(int u, int p) {
    FOR(x,1,V){
        h[u][x][0] = h[u][x][1] = 0;
        for (auto v : al[u]) if (v != p) {
            if (h[u][x][0] == 0 or f[v][x] > f[h[u][x][0]][x]) h[u][x][0] = v;
            else if (h[u][x][1] == 0 or f[v][x] > f[h[u][x][1]][x]) h[u][x][1] = v;
        }
    }

    for (auto v : al[u]) if (v != p) {
        g[v][0] = 0;
        FOR(x,1,V) {
            g[v][x] = max({
                        g[u][x],
                        (h[u][x][0] != v ? f[h[u][x][0]][x] : f[h[u][x][1]][x]),
                        g[u][x-1] + (surr[u] - P[v] + P[p]),
                        (h[u][x-1][0] != v ? f[h[u][x-1][0]][x-1] : f[h[u][x-1][1]][x-1]) + (surr[u] - P[v] + P[p]),
                    });
        }

        up(v,u);
    }

}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> V;
    FOR(i,1,N) { cin >> P[i]; }

    FOR(i,1,N-1) {
        int A, B; cin >> A >> B;
        al[A].push_back(B);
        al[B].push_back(A);
    }

    down(1,0);
    up(1,0);
    ll ans = 0;
    FOR(i,1,N){
        //cout << "i " << i << " :: " << f[i][V] << " " << g[i][V] << " " << (V-1 >= 0 ? g[i][V-1] + surr[i] + P[pa[i]] : 0) << endl;
        ans = max({
                ans,
                f[h[i][V][0]][V],
                (V-1 >= 0 ? f[h[i][V-1][0]][V-1] + surr[i] + P[pa[i]] : 0),
                g[i][V],
                (V-1 >= 0 ? g[i][V-1] + surr[i] + P[pa[i]] : 0)
                });
    }
    cout << ans << '\n';
}

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