| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58055 |
2018-07-16T16:42:27 Z |
wilwxk |
ICC (CEOI16_icc) |
C++11 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int MAXK=102;
vector<int> g[MAXN];
int pai[MAXN], v[MAXN];
long long soma[MAXN], dp[MAXN][MAXK][2];
int n, x;
void predfs(int cur, int p) {
soma[cur]=0; pai[cur]=p;
for(auto viz : g[cur]) {
if(viz==p) continue;
predfs(viz, cur);
soma[cur]+=v[viz];
}
}
int readInt () {
bool minus = false;
int result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus = true; else result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}
long long fazdp(int cur, int k, int flag) {
if(k<0||(k==0&&flag==0)) return 0;
if(dp[cur][k][flag]!=-1) return dp[cur][k][flag];
long long resp=0;
if(flag) {
resp=soma[cur];
for(auto viz : g[cur]) {
if(viz==pai[cur]) continue;
resp=max(resp, fazdp(viz, k, 0)+soma[cur]);
resp=max(resp, fazdp(viz, k-1, 1)+soma[cur]);
}
}
else {
for(auto viz : g[cur]) {
if(viz==pai[cur]) continue;
resp=max(resp, fazdp(viz, k, 0));
resp=max(resp, fazdp(viz, k-1, 1));
}
}
//printf("%d %d %d -> %lld\n", cur, k, flag, resp);
return dp[cur][k][flag]=resp;
}
int main() {
scanf("%d %d", &n, &x);
for(int i=1; i<=n; i++) v[i]=readInt();
for(int i=0; i<n-1; i++) {
int a, b; scanf("%d %d", &a, &b);
g[a].push_back(b); g[b].push_back(a);
}
long long respf=0;
for(int cur=1; cur<=1; cur++) {
predfs(cur, cur);
for(int i=1; i<=n; i++) for(int j=0; j<=x; j++) for(int k=0; k<2; k++) dp[i][j][k]=-1;
for(int i=0; i<=x; i++) respf=max(respf, fazdp(cur, i, 0));
for(int i=1; i<=x; i++) respf=max(respf, fazdp(cur, i-1, 1));
}
if(n<=1005) {
for(int cur=2; cur<=n; cur++) {
predfs(cur, cur);
for(int i=1; i<=n; i++) for(int j=0; j<=x; j++) for(int k=0; k<2; k++) dp[i][j][k]=-1;
for(int i=0; i<=x; i++) respf=max(respf, fazdp(cur, i, 0));
for(int i=1; i<=x; i++) respf=max(respf, fazdp(cur, i-1, 1));
}
}
printf("%lld\n", respf);
}
/*
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
*/
Compilation message
icc.cpp: In function 'int main()':
icc.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &x);
~~~~~^~~~~~~~~~~~~~~~~
icc.cpp:69:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
/tmp/ccwNBbRk.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccIhb3gy.o:icc.cpp:(.text.startup+0x0): first defined here
/tmp/ccwNBbRk.o: In function `main':
grader.cpp:(.text.startup+0x1d): undefined reference to `run'
collect2: error: ld returned 1 exit status
