이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pll pair < ll, ll >
using namespace std;
const int N = 2e5+10;
int n;
vector < pll > edges[N];
vector < pll > takea[N];
vector < pll > takeb[N];
vector < ll > takec[N];
ll dp[N][4]; // dp[x][0] - nastavak ne T-a, dp[x][1] - nastavak T-a ili pocetak T-a, dp[x][2] - nista se ne nastavlja, dp[x][3] - nastavak T-a prema parentu
void dfs( int pos, int par ) {
ll total = 0, parval = -1e9, jedan = -1e9, dva = -1e9, nastavakt = -1e9, nastavaktp = -1e9, total2 = 0;
for(int i = 0; i < (int) edges[pos].size(); i++) {
if(edges[pos][i].f!=par) {
dfs(edges[pos][i].f, pos);
total += max(dp[edges[pos][i].f][0], dp[edges[pos][i].f][2]);
total2 += max(max(dp[edges[pos][i].f][0], dp[edges[pos][i].f][2]), dp[edges[pos][i].f][1]);
takea[pos].pb(mp(dp[edges[pos][i].f][2] - max(dp[edges[pos][i].f][0], dp[edges[pos][i].f][2]) + edges[pos][i].s, edges[pos][i].f));
takeb[pos].pb(mp(dp[edges[pos][i].f][1] - max(dp[edges[pos][i].f][0], dp[edges[pos][i].f][2]) + edges[pos][i].s, edges[pos][i].f));
}
else parval = edges[pos][i].s;
}
sort(takea[pos].begin(), takea[pos].end());
reverse(takea[pos].begin(), takea[pos].end());
sort(takeb[pos].begin(), takeb[pos].end());
reverse(takeb[pos].begin(), takeb[pos].end());
if((int) takea[pos].size() > 0) jedan = parval + takea[pos][0].f;
if((int) takea[pos].size() > 1) dva = takea[pos][1].f + takea[pos][0].f;
if((int) takea[pos].size() > 1 && takea[pos][0].s != takeb[pos][0].s) nastavakt = takea[pos][0].f + takeb[pos][0].f;
if((int) takea[pos].size() > 1 && takea[pos][0].s == takeb[pos][0].s) nastavakt = max(takea[pos][0].f + takeb[pos][1].f, takea[pos][1].f + takeb[pos][0].f);
dp[pos][2] = total2;
dp[pos][0] = total + jedan;
dp[pos][1] = total + max(max(dva, nastavakt), nastavaktp);
if((int) takeb[pos].size() > 0) dp[pos][3] = total + parval + takeb[pos][0].f;
else dp[pos][3] = -1e9;
return;
}
int main( void ) {
FIO
ll tempa, tempb, tempc;
cin >> n;
for(int i = 0; i < n - 1; i++) {
cin >> tempa >> tempb >> tempc;
edges[--tempa].pb(mp(--tempb, tempc));
edges[tempb].pb(mp(tempa, tempc));
}
dfs(0, -1);
cout << max(dp[0][0], max(dp[0][1], dp[0][2])) << "\n";
return 0;
}
# | 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... |