이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
vector <int> v[DIMN];
int frm;
long long dp[2][DIMN][110] , dp2[2][DIMN][110],part[2][DIMN][110] , part2[2][DIMN][110];
long long val[DIMN] , sol;
void dfs (int nod , int tt){
int i , vecin , j;
long long sum;
sum = 0;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != tt){
sum += val[vecin];
}
}
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != tt){
dfs (vecin , nod);
//if (nod == 2 && vecin == 6)
// printf ("a");
for ( j = 0 ; j <= frm ; j++){
/// caz 1 : ai venit de jos in nod, te duci in jos spre vecin
sol = max(sol , dp[0][nod][j] + part2[0][vecin][frm - j]);
if (frm - j)
sol = max(sol , dp[0][nod][j] + part2[1][vecin][frm - j]);
if (j){
sol = max(sol , dp[1][nod][j] + part2[0][vecin][frm - j] + val[tt]);
if (frm - j)
sol = max(sol , dp[1][nod][j] + part2[1][vecin][frm - j] + val[tt]);
}
/// caz 2 : ai venit din jos spre vecin , te duci in nod apoi in jos
sol = max(sol , dp2[0][nod][j] + part[0][vecin][frm - j]);
if (frm - j)
sol = max(sol , dp2[0][nod][j] + part[1][vecin][frm - j] + val[nod]);
if (j){
sol = max(sol , dp2[1][nod][j] + part[0][vecin][frm - j] + val[tt] - val[vecin]);
if (frm - j)
sol = max(sol , dp2[1][nod][j] + part[1][vecin][frm - j] + val[tt] + val[nod] - val[vecin]);
}
//if (nod == 2 && vecin == 6 && sol == 48586232910)
// printf ("%d ",j);
}
//printf ("%d %lld\n",nod,sol);
/// adaugi vecin la setul de vecini cu care ai uni alti vecini
/// (ce coerenta fusei)
/// presupunem ca din vecin vrei sa te duci in nod
dp[1][nod][1] = max ( dp[1][nod][1] , sum );
for (j = 0 ; j <= frm ; j++){ /// vrei ca pana in nod sa fi consumat j
dp[0][nod][j] = max( dp[0][nod][j] , dp[0][vecin][j]);
/// nu ai aplicat nici in nod nici in vecin , ok
if (j)
dp[0][nod][j] = max( dp[0][nod][j] , dp[1][vecin][j] + val[nod]);
/// daca ai aplicat inainte in vecin, jerry nu mai vede in nod
if (j){ /// aplici in nod
/// daca nu am aplicat in vecin inainte
dp[1][nod][j] = max(dp[1][nod][j] , dp[0][vecin][j-1] + sum - val[vecin]);
/// daca am aplicat in vecin inainte
/// jerry nu o sa mai vada valoarea din nod, dra tom oricum o vede
if (j-1)
dp[1][nod][j] = max (dp[1][nod][j] , dp[1][vecin][j-1] + sum - val[vecin] + val[nod]);
}
sol = max(sol , dp[0][nod][j]);
if (j)
sol = max(sol , dp[1][nod][j] + val[tt]);
part[1][nod][j] = max(part[1][nod][j-1] , dp[1][nod][j]);
part[0][nod][j] = max(part[0][nod][j-1] , dp[0][nod][j]);
}
/// acum calculez dp2 , incep din i, ma duc in jos , consum j
dp2[1][nod][1] = max(dp2[1][nod][1] , sum);
for (j = 0 ; j <= frm ; j++){ /// vrei ca pana in nod sa fi consumat j
dp2[0][nod][j] = max( dp2[0][nod][j] , dp2[0][vecin][j]);
/// nu ai aplicat nici in nod nici in vecin , ok
if (j)
dp2[0][nod][j] = max( dp2[0][nod][j] , dp2[1][vecin][j]);
/// daca ai aplicat inainte in vecin, jerry nu mai vede in nod
if (j){ /// aplici in nod
/// daca nu am aplicat in vecin inainte
dp2[1][nod][j] = max(dp2[1][nod][j] , dp2[0][vecin][j-1] + sum);
/// daca am aplicat in vecin inainte
/// jerry nu o sa mai vada valoarea din nod, dra tom oricum o vede
if (j-1)
dp2[1][nod][j] = max (dp2[1][nod][j] , dp2[1][vecin][j-1] + sum);
}
sol = max(sol , dp2[0][nod][j]);
if (j)
sol = max(sol , dp2[1][nod][j] + val[tt]);
part2[1][nod][j] = max(part2[1][nod][j-1] , dp2[1][nod][j]);
part2[0][nod][j] = max(part2[0][nod][j-1] , dp2[0][nod][j]);
}
//printf ("%d %lld\n",nod,sol);
}
}
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , i , x , y;
fscanf (fin,"%d%d",&n,&frm);
for (i=1;i<=n;i++)
fscanf (fin,"%lld",&val[i]);
for (i=1;i<n;i++){
fscanf (fin,"%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs (1 , 0);
fprintf (fout,"%lld" , sol);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
chase.cpp: In function 'void dfs(int, int)':
chase.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
chase.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
chase.cpp: In function 'int main()':
chase.cpp:128:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&n,&frm);
~~~~~~~^~~~~~~~~~~~~~~~~~~~
chase.cpp:130:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%lld",&val[i]);
~~~~~~~^~~~~~~~~~~~~~~~~~~~
chase.cpp:132:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&x,&y);
~~~~~~~^~~~~~~~~~~~~~~~~~
# | 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... |