Submission #120963

#	Time	Username	Problem	Language	Result	Execution time	Memory
120963		BigChungus	Chase (CEOI17_chase)	C++14	0 / 100	242 ms	94200 KiB

chase

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7, V = 102;
const long long INF = 1e11 + 7;///naibii e maxim V * 1e9

long long dp[N][V][2], auxdp[V][2], p[N];

vector < int > adia[N];

int v;
long long ans(0);

void dfs(int nod, int t) {
    int sumvec(0);
    ///hatz ceva precalc
    for (int i : adia[nod])
        if (i != t)
            sumvec += p[i], dfs(i, nod);
    ///hatz calculam dinamica dp[nod][j][0/1] = diferenta maxima obtinuta cand urcam/coboram in nod(nu conteaza) cu j paini
    for (int i : adia[nod]) {
        if (i == t)
            continue;
        for (int j = 1; j <= v; ++j) {///           nu iei j   iei j => scazi p[nod]
            long long x = max(dp[i][j][0], dp[i][j][1] - p[nod]), _x = max(dp[i][j - 1][0], dp[i][j - 1][1] - p[nod]);
            dp[nod][j][0] = max(dp[nod][j][0], x);
            if (j > 1)
                dp[nod][j][1] = max(dp[nod][j][1], sumvec - p[i] + _x);
            else
                dp[nod][j][1] = sumvec;
        }
    }
    ///hatz updatam raspunsul
    ///auxdp[i][0] = din fii vizitati pana acum scorul maxim max(dp[fiu][i][0], dp[fiu][i][1] - p[nod]) E POZITIV
    ///auxdp[i][1] = din fii vizitati pana acum scorul maxim max(dp[fiu][i][0], dp[fiu][i][1] - p[nod]) - p[fiu](ne trebe) POATE FI NEGATIV
    for (int i = 1; i <= v; ++i)
        auxdp[i][0] = 0, auxdp[i][1] = -INF;
    ans = max(ans, max(dp[nod][v][0], dp[nod][v][1]));///(hatz)
    for (int i : adia[nod]) {
        if (i == t)
            continue;
        for (int j = 1; j < v; ++j) {
            long long x = max(dp[i][v - j][0], dp[i][v - j][1] - p[nod]);
            long long _x = x - p[i];
            ans = max(ans, max(
                    x + auxdp[j][0], ///nu il iei pe nod
                    _x + auxdp[j][1] + sumvec///il iei pe nod
                    ));///nu iei niciodata doar de pe o ramura pt ca (hatz)
            auxdp[j][0] = max(auxdp[j][0], x);
            auxdp[j][1] = max(auxdp[j][1], _x);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    int n, a, b;
    cin >> n >> v;

    for (int i = 0; i < n; ++i)
        cin >> p[i];
    for (int i = 1; i < n; ++i) {
        cin >> a >> b;
        adia[a].push_back(b);
        adia[b].push_back(a);
    }

    dfs(1, 0);
    cout << ans;
    return 0;
}
///Nu e corect, dar ma dau batut

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