Submission #25637

#	Time	Username	Problem	Language	Result	Execution time	Memory
25637		szawinis	Uzastopni (COCI15_uzastopni)	C++14	0 / 160	0 ms	1844 KiB

uzastopni

#include <bits/stdc++.h>
using namespace std;
const int MAX = (5e5)+1;

int n, k, sum[MAX];
long long dp[MAX], mxp[MAX], ans[MAX];
pair<long long, int> l[MAX][2];
vector<pair<int,int> > g[MAX];
bool need[MAX];

void dfs1(int u, int par) {
	sum[u] = need[u];
	for(auto p: g[u]) {
		int v, w;
		tie(v, w) = p;
		if(v != par) {
			dfs1(v, u);
			sum[u] += sum[v];
			if(!sum[v]) continue;
			dp[u] += dp[v] + 2*w;
			if(l[v][0].first + w > l[u][0].first) {
				l[u][1] = l[u][0];
				l[u][0] = {l[v][0].first + w, v};
			} else if(l[v][0].first + w > l[u][1].first) {
				l[u][1] = {l[v][0].first + w, v};
			}
		}
	}
}

void dfs2(int u, int par, long long up = 0) {
	ans[u] = up + dp[u] - max(mxp[u], l[u][0].first);
	for(auto p: g[u]) {
		int v, w;
		tie(v, w) = p;
		if(v != par) {
			long long tmp = (v == l[u][0].second ? l[u][1].first : l[u][0].first);
			mxp[v] = max((tmp || sum[u] - sum[v])*(tmp + w), bool(mxp[u])*(mxp[u] + w));
			dfs2(v, u, up + (up || sum[u] - sum[v])*(dp[u] - dp[v] + !bool(sum[v])*2*w));
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for(int i = 1, u, v, w; i < n; i++) {
		cin >> u >> v >> w;
		g[u-1].emplace_back(v-1, w);
		g[v-1].emplace_back(u-1, w);
	}
	for(int i = 0, v; i < k; i++) cin >> v, need[v-1] = true;
	dfs1(0, -1);
	dfs2(0, -1);
	for(int i = 0; i < n; i++) cout << ans[i] << '\n';
}

• Subtask 1: 0 / 160