Submission #220167

#	Time	Username	Problem	Language	Result	Execution time	Memory
220167		manh9203	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	456 ms	55416 KiB

designated_cities

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
typedef pair<ll, ll> pii;
const int N = 2e5 + 5;

int n, q;
vector<pair<int, pii> > adj[N];
ll curSum, Max, root;
ll ans[N], sum[N];
pii maxChild[N];
int par[N], val[N];
int check[N];

ll dfs1(int u, int p) {
	ll res = 0;
	for (auto e : adj[u]) {
		int v = e.fi;
		if (v != p) {
			res += dfs1(v, u) + e.se.se;
		}
	}
	return res;
}

void dfs2(int u, int p) {
	Max = max(Max, curSum);
	sum[u] = curSum;
	for (auto e : adj[u]) {
		int v = e.fi;
		if (v != p) {
			curSum += e.se.fi - e.se.se;
			dfs2(v, u);
			curSum += e.se.se - e.se.fi;
		}
	}
}

ll dist[N], distVal[N];
ll maxVer[N];
ll mx;
pair<int, int> best;

void dfs3(int u, int p) {
	distVal[u] = sum[u] + dist[u];
	maxVer[u] = u;
	for (auto e : adj[u]) {
		int v = e.fi;
		if (v != p) {
			dist[v] = dist[u] + e.se.fi + e.se.se;
			dfs3(v, u);
			if (distVal[maxVer[v]] + distVal[maxVer[u]] - 2 * dist[u] > mx) {
				mx = distVal[maxVer[v]] + distVal[maxVer[u]] - 2 * dist[u];
				best = {maxVer[u], maxVer[v]};
			}
			if (distVal[maxVer[v]] > distVal[maxVer[u]]) {
				maxVer[u] = maxVer[v];
			}
		}
	}
}

void dfs(int u, int p) {
	maxChild[u] = {val[u], u};
	for (auto e : adj[u]) {
		int v = e.fi;
		if (v != p) {
			par[v] = u;
			val[v] = e.se.fi;
			dfs(v, u);
			if (maxChild[v].fi + val[u] > maxChild[u].fi) {
				maxChild[u].fi = maxChild[v].fi + val[u];
				maxChild[u].se = maxChild[v].se;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;
	ll sumEdge = 0;
	for (int i = 1; i < n; i++) {
		int u, v, a, b;
		cin >> u >> v >> a >> b;
		adj[u].push_back({v, {a, b}});
		adj[v].push_back({u, {b, a}});
		sumEdge += a + b;
	}
	curSum = dfs1(1, 1); 
	dfs2(1, 1);
	
	dfs3(1, 1);
	root = best.fi;
	ans[1] = sum[root];
	dfs(root, root);
	priority_queue<pii> pq;
	pq.push(maxChild[root]);
	for (int i = 2; i <= n; i++) {
		ans[i] = ans[i - 1];
		if (pq.size() > 0) {
			ans[i] += pq.top().fi;
			int u = pq.top().se;
			pq.pop();
			while (u != 0 && check[u] == 0) {
				check[u] = 1;
				for (auto e : adj[u]) {
					if (e.fi != par[u] && check[e.fi] == 0) {
						pq.push(maxChild[e.fi]);
					}
				}
				u = par[u];
			}
		}
	}
	ans[1] = Max;
	
	cin >> q;
	while (q--) {
		int x;
		cin >> x;
		cout << sumEdge - ans[x] << "\n";
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44