Submission #996829

#	Time	Username	Problem	Language	Result	Execution time	Memory
996829		violet_valley	Chase (CEOI17_chase)	C++17	20 / 100	510 ms	332888 KiB

chase

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define PR(a,n) { cerr << #a << " = "; FOR(_,1,n) cerr << a[_] << ' '; cerr << endl; }
#define PR0(a,n) { cerr << #a << " = "; REP(_,n) cerr << a[_] << ' '; cerr << endl; }
#define debug(x) cerr << #x << " = " << x << endl
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1 << (i))
#define FULL(i) (MASK(i) - 1)
#define __builtin_popcount __builtin_popcountll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <class T, class T2>
ostream &operator<<(ostream &o, pair<T, T2> p)
{
    o << "(" << p.first << ", " << p.second << ")";
    return o;
}
const int M = 1e5 + 5, N = 102;
const ll INF = 1e15;
ll f[M][N][4], a[M];
vector <int> adj[M];
int n, m;
int next_state(int mask, int nxt)
{
    return ((mask << 1) | nxt) & 3;
}
void reset()
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= m; ++j)
        {
            for (int k = 0; k < 4; ++k)
                f[i][j][k] = -INF;
        }
    }
}
void dfs(int u, int par = 0)
{
    ll sum = 0;
    for (auto v: adj[u])
        sum += a[v];
    if (par && adj[u].size() == 1)
    {
        f[u][0][0] = 0, f[u][1][1] = sum;
        return;
    }
    for (auto v: adj[u])
    {
        if (v == par)
            continue;
        dfs(v, u);
        for (int val = 0; val <= m; ++val)
            for (int mask = 0; mask < 4; ++mask)
            {
                int tmp = next_state(mask, 0);
                // debug(tmp);
                f[u][val][tmp] = max(f[u][val][tmp], f[v][val][mask]);
            }
        for (int val = 1; val <= m; ++val)
        {
            f[u][val][1] = max(f[u][val][1], f[v][val - 1][0] + sum);
            for (int mask = 1; mask < 4; ++mask)
            {
                int tmp = next_state(mask, 1);
                // debug(tmp);
                f[u][val][tmp] = max(f[u][val][tmp], f[v][val - 1][mask] + sum - a[v]);
            }
        }
    }
}

ll process(int i)
{
    reset();
    dfs(i);
    // for (int i = 1; i <= n; ++i)
    // {
    //     cout << i << endl;
    //     for (int val = 0; val <= m; ++val)
    //     {
    //         cout << make_pair(f[i][val][0], f[i][val][1]) << " ";
    //     }
    //     cout << endl;
    // }
    ll tmp = -INF;
    for (int val = 0; val <= m; ++val)
        for (int ok = 0; ok < 4; ++ok)
            tmp = max(tmp, f[i][val][ok]);
    return tmp;
}
signed main()
{
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // LOCAL
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    ll res = -INF;
    
    if (n <= 1000)
    {
        for (int i = 1; i <= n; ++i)
        {
            // debug(process(i));
            res = max(res, process(i));
        }
    }
    else
        res = process(1);
    cout << res;
}

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