#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <map>
#define N 200'005
long long n;
long long k;
long long l;
long long ans = INT_MIN;
long long a[N];
long long u[N];
long long v[N];
std::vector<std::pair<long long, std::pair<long long, long long>>> g[N];
std::vector<long long> pre[N];
std::map <long long, long long> yer[N];
int main() {
std::cin >> n >> l >> k;
for (long long i = 1; i <= n; ++i) {
std::cin >> a[i];
}
for (long long i = 1; i < n; ++i) {
std::cin >> u[i] >> v[i];
long long vyer = g[u[i]].size();
long long uyer = g[v[i]].size();
g[u[i]].push_back(std::make_pair(a[v[i]], std::make_pair(v[i], uyer)));
g[v[i]].push_back(std::make_pair(a[u[i]], std::make_pair(u[i], vyer)));
}
for (long long i = 1; i <= n; ++i) {
sort(g[i].begin(), g[i].end());
reverse(g[i].begin(), g[i].end());
}
for (size_t i = 1; i <= n; ++i) {
for (long long j = 0; j < g[i].size(); ++j) {
yer[g[i][j].second.first][i] = j;
}
}
for (long long i = 1; i <= n; ++i) {
ans = std::max(ans, a[i]);
}
if (k == 1) {
std::cout << ans << "\n";
return 0;
}
for (long long i = 1; i <= n; ++i) {
long long mx = 0;
long long top = 0;
for (long long j = 0; j < g[i].size(); ++j) {
top += g[i][j].first;
mx = std::max(mx, top);
pre[i].push_back(mx);
}
}
for (long long i = 1; i <= n; ++i) {
long long top = a[i];
ans = std::max(ans, top);
for (long long j = 0; j < std::min(k - 1, (long long)g[i].size()); ++j) {
top += g[i][j].first;
ans = std::max(ans, top);
}
ans = std::max(ans, top);
}
if (l == 3) {
for (long long i = 1; i < n; ++i) {
long long top = a[u[i]] + a[v[i]];
ans = std::max(ans, top);
long long geldi = 0;
if ((long long)g[u[i]].size() < (long long)g[v[i]].size()) {
long long uyer = yer[u[i]][v[i]];
for (long long j = 0; j < std::min(k - 2, (long long)g[u[i]].size()); ++j) {
if (g[u[i]][j].second.first == v[i]) {
geldi = 1;
continue;
}
long long bak = k - (j - geldi + 1 + 2) - 1;
long long ek = 0;
if (bak >= 0) {
if (bak >= uyer) {
if (a[u[i]] < 0) {
if (uyer >= 1) {
ek = pre[v[i]][uyer - 1];
}
}
else {
ek = pre[v[i]][std::min(bak + 1, (long long)pre[v[i]].size() - 1)] - a[u[i]];
}
}
else {
ek = pre[v[i]][std::min(bak, (long long)pre[v[i]].size() - 1)];
}
}
top += g[u[i]][j].first;
ans = std::max(ans, top + ek);
}
}
else {
long long vyer = yer[v[i]][u[i]];
for (long long j = 0; j < std::min(k - 2, (long long)g[v[i]].size()); ++j) {
if (g[v[i]][j].second.first == u[i]) {
geldi = 1;
continue;
}
long long bak = k - (j - geldi + 1 + 2) - 1;
long long ek = 0;
if (bak >= 0) {
if (bak >= vyer) {
if (a[v[i]] < 0) {
ek = pre[u[i]][vyer - 1];
}
else {
ek = pre[u[i]][std::min(bak + 1, (long long)pre[u[i]].size() - 1)] - a[v[i]];
}
}
else {
ek = pre[u[i]][std::min(bak, (long long)pre[u[i]].size() - 1)];
}
}
top += g[v[i]][j].first;
ans = std::max(ans, top + ek);
}
}
}
}
std::cout << ans << "\n";
return 0;
}N = 200005
n = 0
k = 0
l = 0
ans = -(2**31)
a = [0 for x in range(N)]
u = [0 for x in range(N)]
v = [0 for x in range(N)]
#g = [[]] * N
g = [[] for x in range(N)]
pre = [[] for x in range(N)]
yer = [{} for x in range(N)]
n, l, k = [int(x) for x in input().split()]
a[1:n + 1] = [int(x) for x in input().split()]
for i in range(1, n):
u[i], v[i] = [int(x) for x in input().split()]
vyer = len(g[u[i]])
uyer = len(g[v[i]])
g[u[i]].append([a[v[i]], [v[i], uyer]])
g[v[i]].append([a[u[i]], [u[i], vyer]])
for i in range(1, n + 1):
#sorted(g[i], reverse=True)
sorted(g[i])
g[i].reverse()
for i in range(1, n + 1):
for j in range(len(g[i])):
yer[g[i][j][1][0]][i] = j
for i in range(1, n + 1):
ans = max(ans, a[i])
if k == 1:
print(ans)
exit()
for i in range(1, n + 1):
mx = 0
top = 0
for j in range(len(g[i])):
top += g[i][j][0]
mx = max(mx, top)
pre[i].append(mx)
for i in range(1, n + 1):
top = a[i]
ans = max(ans, top)
for j in range(min(k - 1, len(g[i]))):
top += g[i][j][0]
ans = max(ans, top)
ans = max(ans, top)
if l == 3:
for i in range(1, n):
top = a[u[i]] + a[v[i]]
ans = max(ans, top)
geldi = 0
if len(g[u[i]]) < len(g[v[i]]):
uyer = yer[u[i]][v[i]]
for j in range(min(k - 2, len(g[u[i]]))):
if g[u[i]][j][1][0] == v[i]:
geldi = 1
j += 1
continue
bak = k - (j - geldi + 1 + 2) - 1
ek = 0
if bak >= 0:
if bak >= uyer:
if a[u[i]] < 0:
if uyer >= 1:
ek = pre[v[i]][uyer - 1]
else:
ek = pre[v[i]][min(
bak + 1, len(pre[v[i]]) - 1)] - a[u[i]]
else:
ek = pre[v[i]][min(bak, len(pre[v[i]]) - 1)]
top += g[u[i]][j][0]
ans = max(ans, top + ek)
else:
vyer = yer[v[i]][u[i]]
for j in range(min(k - 2, len(g[v[i]]))):
if g[v[i]][j][1][0] == u[i]:
geldi = 1
j += 1
continue
bak = k - (j - geldi + 1 + 2) - 1
ek = 0
if bak >= 0:
if bak >= vyer:
if a[v[i]] < 0:
ek = pre[u[i]][vyer - 1]
else:
ek = pre[u[i]][min(
bak + 1, len(pre[u[i]]) - 1)] - a[v[i]]
else:
ek = pre[u[i]][min(bak, len(pre[u[i]]) - 1)]
top += g[v[i]][j][0]
ans = max(ans, top + ek)
print(ans)
"Muhtemelen".
Projede tüm istenen sadece bu soruyu Python'a çevirmeniz ise o zamana kadar yaparım.
