제출 #1174917

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174917		guilhermecpp	Beads and wires (APIO14_beads)	C++20	0 / 100	3 ms	4936 KiB

beads

#include <bits/stdc++.h>
using namespace std;
 
#define N 200010
#define INF 1000000000000000000
#define fi first
#define se second
#define pb push_back
 
typedef long long ll;
typedef pair< ll, ll > pll;
typedef vector< ll > vl;
typedef vector< pll > vll;

ll n;
vll grafo[N];

ll dp[N][2];
// 0: aresta do pai não foi pega
// 1: aresta do pai já foi pega

void DFS(ll u, ll pai, ll wpai)
{

	ll sum, a, b;

	sum = 0;
	a = -INF;
	b = -INF;

	for(auto [v, w] : grafo[u])
	{

		if(v == pai) continue;

		DFS(v, u, w);

		sum += dp[v][0];

		b = max(b, (dp[v][1] + w) - dp[v][0]);
		if(a < b) swap(a, b);

	}

	dp[u][1] = sum;
	dp[u][1] = max(dp[u][1], sum + a + b);

	dp[u][0] = dp[u][1];
	dp[u][0] = max(dp[u][0], sum + a + wpai);

	return;

}

int main()
{
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

	ll u, v, w, i;

	cin >> n;

	for(i = 1;i < n;i++)
	{

		cin >> u >> v >> w;

		grafo[u].pb({v, w});
		grafo[v].pb({u, w});

	}

	ll x = 0;

	DFS(1, 1, -INF);
	x = dp[1][1];

	for(i = 1;i <= n;i++)
	{

		DFS(i, i, -INF);
		if(dp[i][1] != x) assert(false);

	}

	cout << x << endl;

    return 0;
 
} 

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43