Submission #345427

#	Time	Username	Problem	Language	Result	Execution time	Memory
345427		alireza_kaviani	Beads and wires (APIO14_beads)	C++17	100 / 100	260 ms	23976 KiB

beads

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

    return 0;
}
/*

*/

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