Submission #97159

#	Time	Username	Problem	Language	Result	Execution time	Memory
97159		tieunhi	Paprike (COI18_paprike)	C++14	100 / 100	159 ms	22008 KiB

paprike

#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define pii pair<int, int>
#define PB push_back
#define mp make_pair
#define F first
#define S second
#define N 100005
#define maxc 1000000

using namespace std;

int n, k, res;
vector<int> a[N];
vector<ll> vv[N];
ll val[N];

void DFS(int u, int p)
{
    for (auto v : a[u])
    {
        if (v == p) continue;
        DFS(v, u);
        val[u] += val[v];
        vv[u].PB(val[v]);
    }
    sort(vv[u].begin(), vv[u].end());
    reverse(vv[u].begin(), vv[u].end());

    for (auto v : vv[u])
    {
        if (val[u] <= k) break;
        res++;
        val[u] -= v;
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    //freopen("OUT.TXT", "w", stdout);
    cin >> n >> k;
    FOR(i, 1, n) cin >> val[i];
    FOR(i, 2, n)
    {
        int u, v; cin >> u >> v;
        a[u].PB(v);
        a[v].PB(u);
    }
    DFS(1, -1);
    cout <<res;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 27 / 27
• Subtask 4: 49 / 49