제출 #382313

#제출 시각아이디문제언어결과실행 시간메모리
382313pure_mem구슬과 끈 (APIO14_beads)C++14
0 / 100
3 ms2688 KiB
#include <iostream>
#include <vector>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e5 + 12;
const int INF = 1e9;

int n, dp[2][N], ans;
vector< pair<int, int> > g[N];

void dfs(int v, int pr){
	dp[0][v] = -INF;
	for(pair<int, int> tmp: g[v]){
		int to = tmp.X, cost = tmp.Y;
		if(to != pr){
			dfs(to, v);
			dp[1][v] += max(dp[1][to], dp[0][to] + cost);	
		}
	} 
	int sum = dp[1][v], c1 = -INF, c2 = -INF;
	for(pair<int, int> tmp: g[v]){
		int to = tmp.X, cost = tmp.Y;
		if(to != pr){
			int dt = cost;
			if(dp[1][to] < dp[0][to] + cost)
				dt = dp[1][to] - dp[0][to];
			if(c1 < dt)
				c2 = c1, c1 = dt;
			else if(c2 < dt)
				c2 = dt;
		}
	}
	if(c1 != -INF)
		dp[0][v] = sum + c1;
	if(c2 != -INF)
		dp[1][v] = max(dp[1][v], sum + c2 + c1);
	ans = max(ans, dp[1][v]);
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1, x, y, z;i < n;i++){
		cin >> x >> y >> z;
		g[x].push_back(MP(y, z));
		g[y].push_back(MP(x, z));
	}
	dfs(1, 1);
	//cerr << dp[0][6] << "\n";
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...