Submission #1370618

#TimeUsernameProblemLanguageResultExecution timeMemory
1370618kaiboyDesignated Cities (JOI19_designated_cities)C++20
16 / 100
115 ms41944 KiB
#include <algorithm>
#include <iostream>

using namespace std;

const       int   N = 200000;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

int ij[N], ww[N << 1], *eh[N], eo[N];
long long ss[N], tt[N]; int ii[N];
long long x1, x2; int i2, j2;
long long ans[N + 1];

void append(int i, int h) {
	int o = eo[i]++;
	if (!o)
		eh[i] = (int *) malloc(sizeof *eh[i]);
	else
		eh[i] = (int *) realloc(eh[i], (o << 1) * sizeof *eh[i]);
	eh[i][o] = h;
}

long long dfs(int p, int i) {
	long long s = 0;
	for (int o = 0; o < eo[i]; o++) {
		int h = eh[i][o], j = i ^ ij[h >> 1], w = ww[h];
		if (j != p)
			s += w + dfs(i, j);
	}
	return ss[i] = s;
}

void dfs(int p, int i, long long s_) {
	long long s = 0;
	for (int o = 0; o < eo[i]; o++) {
		int h = eh[i][o], j = i ^ ij[h >> 1], w = ww[h];
		if (j != p)
			s += w + ss[j];
	}
	x1 = min(x1, s + s_);
	if (p != -1 && eo[i] == 1) {
		tt[i] = 0, ii[i] = i;
		return;
	}
	long long t_ = INF; int j_ = -1;
	for (int o = 0; o < eo[i]; o++) {
		int h = eh[i][o], j = i ^ ij[h >> 1], w = ww[h];
		if (j != p) {
			dfs(i, j, s + s_ + ww[h ^ 1] - (w + ss[j]));
			long long t = tt[j] - (w + ss[j]);
			if (j_ != -1) {
				long long x = s + s_ + t + t_;
				if (x2 > x)
					x2 = x, i2 = ii[j], j2 = ii[j_];
			}
			if (t_ > t)
				t_ = t, j_ = j;
		}
	}
	tt[i] = s + t_, ii[i] = j_;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	for (int h = 0; h < n - 1; h++) {
		int i, j, w, w_; cin >> i >> j >> w >> w_, i--, j--;
		ij[h] = i ^ j, ww[h << 1 ^ 0] = w, ww[h << 1 ^ 1] = w_;
		append(i, h << 1 ^ 0), append(j, h << 1 ^ 1);
	}
	dfs(-1, 0);
	x1 = x2 = INF;
	dfs(-1, 0, 0);
	ans[1] = x1, ans[2] = min(x2, tt[0]);
	int q; cin >> q;
	while (q--) {
		int k; cin >> k;
		cout << ans[k] << '\n';
	}
	return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...