제출 #982732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982732		vjudge1	Chase (CEOI17_chase)	C++17	0 / 100	31 ms	8020 KiB

chase

#include <bits/stdc++.h>
#define pii pair<int,int>
#define int long long
#define ff first
#define ss second
using namespace std;

void solve()
{
    int n,br;
    cin >> n >> br;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    vector<vector<int>> tree(n);
    for (int i = 0; i < n-1; i++)
    {
        int a,b;
        cin >> a >> b;
        --a;--b;
        tree[a].push_back(b);
        tree[b].push_back(a);
        
    }
    vector<int> dsum(n,0);
    for (int i = 0; i < n; i++)
        for (auto a : tree[i])
            dsum[i]+=v[a];
    int ans = 0;
    if (n <= 1001)
        for (int i = 0; i < n; i++)
        {
            queue<array<int,3>> bfs;
            bfs.push({i,dsum[i],1});
            vector<bool> vis(n,0);
            vis[i] = 1;
            while (!bfs.empty())
            {
                auto a = bfs.front();
                ans = max(ans,a[1]);
                for (auto u : tree[a[0]])
                {
                    if (!vis[u])
                    {
                        vis[u]  =1;
                        if (a[2]+1 <= br)
                            bfs.push({u,a[1]+dsum[u]-v[a[0]],a[2]+1});
                    }
                }
                bfs.pop();
            }
        }
    else
    {
        int i = 0;
        queue<array<int,3>> bfs;
        bfs.push({i,dsum[i],1});
        vector<bool> vis(n,0);
        vis[i] = 1;
        while (!bfs.empty())
        {
            auto a = bfs.front();
            ans = max(ans,a[1]);
            for (auto u : tree[a[0]])
            {
                if (!vis[u])
                {
                    vis[u]  =1;
                    if (a[2]+1 <= br)
                        bfs.push({u,a[1]+dsum[u]-v[u]-v[a[0]],a[2]+1});
                }
            }
            bfs.pop();
        }
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
   
       solve();
    
    
    
    return 0;
}

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