Submission #585563

#	Time	Username	Problem	Language	Result	Execution time	Memory
585563		amunduzbaev	Chase (CEOI17_chase)	C++17	0 / 100	44 ms	13492 KiB

chase

#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]);
			}
		}
		
		if(n > 1000) break;
	}
	
	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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30