oj.uz

답안 #345424

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
345424 2021-01-07T09:29:15 Z alireza_kaviani 구슬과 끈 (APIO14_beads) C++17
0 / 100
 5 ms 5100 KB 
#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] , dpUp[MAXN][2] , W[MAXN];
vector<pii> adj[MAXN];

void DFSDown(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;
		DFSDown(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;
}

void DFSUp(int v , int p = -1 , int w = -MOD){
	W[v] = w;
	int sum = max(dpUp[v][0] , dpUp[v][1] + w) , mx = dpUp[v][0] + w - max(dpUp[v][0] , dpUp[v][1] + w);
	for(pii i : adj[v]){
		int u = i.X , w = i.Y;
		if(u == p)	continue;
		sum += max(dpDown[u][0] , dpDown[u][1] + w);
		dpUp[u][1] = mx;
		mx = max(mx , dpDown[u][0] + w - max(dpDown[u][0] , dpDown[u][1] + w));
	}
	mx = -MOD;
	reverse(all(adj[v]));
	for(pii i : adj[v]){
		int u = i.X , w = i.Y;
		if(u == p)	continue;
		dpUp[u][1] = max(dpUp[u][1] , mx);
		dpUp[u][0] = sum - max(dpDown[u][0] , dpDown[u][1] + w);
		dpUp[u][1] = dpUp[u][0] + mx;
		mx = max(mx , dpDown[u][0] + w - max(dpDown[u][0] , dpDown[u][1] + w));
		DFSUp(u , v , w);
	}
	//cout << v << sep << dpDown[v][0] << sep << dpDown[v][1] << sep << dpUp[v][0] << sep << dpUp[v][1] << endl;
}

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});
	}
	DFSDown(1);
	DFSUp(1);
	for(int i = 1 ; i <= n ; i++){
		ans = max(ans , dpDown[i][0] + max(dpUp[i][0] , dpUp[i][1] + W[i]));
	}
	cout << ans << endl;

    return 0;
}
/*

*/

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Incorrect 4 ms 5100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Incorrect 4 ms 5100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Incorrect 4 ms 5100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Incorrect 4 ms 5100 KB Output isn't correct
4 Halted 0 ms 0 KB -