# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
101616 | cheeheng | Chase (CEOI17_chase) | C++14 | 103 ms | 27316 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
long long p[100005];
long long p2[100005];
vector<int> AdjList[100005];
int parent[100005];
vector<int> AdjList2[100005];
int dist[100005];
long long memo[1005][105][2];
long long dp(int u, int b, bool taken){
if(AdjList2[u].empty()){
// leaf node
if(b >= 1 && !taken && parent[u] != -1){
return p[parent[u]];
}else{
return 0;
}
}else if(b == 0){
return 0;
}else if(memo[u][b][taken] != -1){
return memo[u][b][taken];
}else{
long long temp = 0;
long long score = 0;
for(int v: AdjList2[u]){
score += p[v];
}
if(!taken && parent[u] != -1){
score += p[parent[u]];
}
for(int v: AdjList2[u]){
temp = max(temp, score+dp(v, b-1, 1));
temp = max(temp, dp(v, b-1, 0));
}
return memo[u][b][taken] = temp;
}
}
int main(){
int N, v;
scanf("%d%d", &N, &v);
for(int i = 1; i <= N; i ++){
scanf("%d", &p[i]);
p2[i] = p[i];
}
for(int i = 1; i < N; i ++){
int a, b;
scanf("%d%d", &a, &b);
AdjList[a].push_back(b);
AdjList[b].push_back(a);
}
long long ans = 0;
for(int i = 1; i <= N; i ++){
queue<int> q;
q.push(i);
memset(dist, -1, sizeof(dist));
dist[i] = 0;
for(int j = 1; j <= N; j ++){
AdjList2[j].clear();
}
while(!q.empty()){
int u = q.front(); q.pop();
for(int v: AdjList[u]){
if(dist[v] == -1){
dist[v] = dist[u] + 1;
parent[v] = u;
AdjList2[u].push_back(v);
q.push(v);
}
}
}
memset(memo, -1, sizeof(memo));
long long temp = dp(i, v, 1);
ans = max(ans, temp);
}
printf("%lld", ans);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |