Submission #113932

#	Time	Username	Problem	Language	Result	Execution time	Memory
113932		MAMBA	Chase (CEOI17_chase)	C++17	100 / 100	904 ms	330980 KiB

chase

#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef complex<ld> point;
typedef pair<ld , ld> pld;
typedef vector<ll> vi;

inline void fileIO(string s) {
	//	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }

constexpr int N = 1e5 + 10;
constexpr int MOD = 1e9 + 7;

template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }

int n;
ll dp_up[N][2][101], dp_down[N][2][101], v2, p[N], p2[N];
vi adj[N];

inline void update(ll A[][101] , ll B[][101] ,int so ,int sy) {
	rep(j , 0 , v2) {
		smax(A[0][j] , B[0][j]);
		smax(A[0][j] , B[1][j] - p[so]);
		if (j) {
			smax(A[1][j] , B[0][j - 1] + p2[so]);
			smax(A[1][j] , B[1][j - 1] + p2[so] - p[so]);
		}
	}
}

void dfs_down(int v, int par = 0) {
	dp_down[v][1][0] = dp_up[v][1][0] = -1e18;
	rep(i , 1 , v2)
		dp_down[v][1][i] = dp_up[v][1][i] = p2[v];
	for (auto e : adj[v]) 
		if (e ^ par) {
			dfs_down(e , v);
			update(dp_down[v] , dp_down[e] , v , e);
		}
}

ll junk[2][101];
void dfs_up(int v, int par = 0) {
	auto f = [v , par]() -> void {
		memcpy(junk , dp_up[v] , sizeof(dp_up[v]));		
		for (auto e : adj[v]) 
			if (e ^ par) {
				update(dp_up[e] , junk , e , v);
				update(junk , dp_down[e] , v , e);
			}
	};
	f();
	reverse(all(adj[v]));
	f();
	for (auto e : adj[v])
		if (e ^ par)
			dfs_up(e , v);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> v2;

	if (v2 == 0) return cout << 0 << endl, 0;
	v2++;

	rep(i , 1 , n + 1) 
		cin >> p[i];
	rep(i , 1 , n) {
		int u , v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
		p2[u] += p[v];
		p2[v] += p[u];
	}

	dfs_down(1);

	dfs_up(1);

	ll res = 0;
	rep(i , 1, n + 1) {
		smax(res , max(dp_up[i][1][v2 - 1] , dp_up[i][0][v2 - 1]));
		smax(res , max(dp_down[i][1][v2 - 1] , dp_down[i][0][v2 - 1]));
	}
	cout << res << endl;

	return 0;
}

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