oj.uz

Submission #585562

# Submission time Handle Problem Language Result Execution time Memory
585562 2022-06-29T05:10:13 Z amunduzbaev Chase (CEOI17_chase) C++17
0 / 100
 4000 ms 15540 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll

const int N = 1e5 + 5;
vector<int> edges[N];
int a[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, v; cin>>n>>v;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	int res = 0;
	for(int i=1;i<=n;i++){
		int d[n + 1] {}, pref[n + 1] {};
		
		function<void(int, int)> dfs = [&](int u, int p){
			for(auto x : edges[u]){
				if(x == p) continue;
				pref[u] += a[x];
			}
			for(auto x : edges[u]){
				if(x == p) continue;
				pref[x] = pref[u];
				d[x] = d[u] + 1;
				dfs(x, u);
			}
		};
		
		pref[i] = a[i];
		dfs(i, i);
		for(int j=1;j<=n;j++){
			if(d[j] + 1 == v){
				res = max(res, pref[j] - a[i]);
			}
		}
	}
	
	cout<<res<<"\n";
}

/*

12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12

*/

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4022 ms 15540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -