제출 #345398

#제출 시각아이디문제언어결과실행 시간메모리
345398alireza_kavianiBeads and wires (APIO14_beads)C++17
28 / 100
1060 ms5612 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define SZ(x)                       ll(x.size())

ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}

const ll MAXN = 2e5 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 2e9 + 7; // 998244353; // 1e9 + 9;

int n , ans , dpDown[MAXN][2];
vector<pii> adj[MAXN];

void DFS(int v , int p = -1){
	dpDown[v][0] = dpDown[v][1] = 0;
	int mx = -MOD;
	for(pii i : adj[v]){
		int u = i.X , w = i.Y;
		if(u == p)	continue;
		DFS(u , v);
		dpDown[v][0] += max(dpDown[u][0] , dpDown[u][1] + w);
		dpDown[v][1] += max(dpDown[u][0] , dpDown[u][1] + w);
		mx = max(mx , dpDown[u][0] + w - max(dpDown[u][0] , dpDown[u][1] + w));
	}
	dpDown[v][1] += mx;
}

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

	cin >> n;
	if(n > 10000)	return 0;
	for(int i = 1 ; i < n ; i++){
		int v , u , w;
		cin >> v >> u >> w;
		adj[v].push_back({u , w});
		adj[u].push_back({v , w});
	}
	for(int i = 1 ; i <= n ; i++){
		DFS(i);
		ans = max(ans , dpDown[i][0]);
	}
	cout << ans << endl;

    return 0;
}
/*

*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...