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 <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef vector<long long> vi;
vector<vi> g;
vector<vector<vector<long long> > > m;
vi d;
//gives the max difference
long long solve(long long n, long long p, long long v){
if(v==0)
return 0;
// if(m[n][p][v]!=-1)
// return m[n][p][v];
long long sum = 0;
for(long long x=0; x<g[n].size(); x++){
if(g[n][x]!=p){
sum += d[g[n][x]];
}
}
long long sol = sum;
for(long long x=0; x<g[n].size(); x++){
if(g[n][x]!=p){
if(m[n][x][v]==-1)
m[n][x][v] = solve(g[n][x], n, v);
if(m[n][x][v-1]==-1)
m[n][x][v-1] = solve(g[n][x], n, v-1);
sol = max(sol, max(sum+m[n][x][v-1], m[n][x][v]));
}
}
return sol;//m[n][p][v] = sol;
}
int main(){
iostream::sync_with_stdio(false); cin.tie(0);
// memset(m, -1, sizeof(m));
long long N, V; cin>>N>>V;
g.assign(N+1, vi());
d.assign(N+1, 0);
long long A, B;
for(long long n=1; n<=N; n++)
cin>>d[n];
for(long long n=1; n<N; n++){
cin>>A>>B;
g[A].push_back(B);
g[B].push_back(A);
}
m.assign(N+1, vector<vector<long long> >());
for(int x=1; x<=N; x++)
m[x].assign(g[x].size(), vector<long long>(110, -1));
long long sol = 0;
sol = solve(1, 0, V);
for(long long x=2; x<=N&&N<10000; x++)
sol = max(sol, solve(x, 0, V));
cout << sol << endl;
return 0;
}
Compilation message (stderr)
chase.cpp: In function 'long long int solve(long long int, long long int, long long int)':
chase.cpp:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long long x=0; x<g[n].size(); x++){
~^~~~~~~~~~~~
chase.cpp:25:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long long x=0; x<g[n].size(); x++){
~^~~~~~~~~~~~
# | 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... |