Submission #376196

#	Time	Username	Problem	Language	Result	Execution time	Memory
376196		8e7	Designated Cities (JOI19_designated_cities)	C++14	39 / 100	403 ms	38508 KiB

designated_cities

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#define ll long long
#define maxn 200005
#define pii pair<int, ll>
#define ff first
#define ss second
#define mod 1000000007
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

vector<pii> adj[maxn];

ll tup[maxn], up[maxn], best[maxn], bind[maxn], ans[maxn];
int par[maxn];
bool done[maxn];
void dfs(int n, int pa) {
	par[n] = pa;
	for (auto v:adj[n]) {
		if (v.ff != pa) {
			dfs(v.ff, n);
			tup[n] += tup[v.ff] + up[v.ff];
			if (v.ss + best[v.ff] > best[n]) {
				best[n] = v.ss + best[v.ff];
				bind[n] = bind[v.ff] == 0 ? v.ff : bind[v.ff];
			}
		} else {
			up[n] = v.ss;
		}
	}
}
void reroot(int u, int v, ll w) {
	tup[u] -= tup[v] + up[v];
	up[u] = w;
	tup[v] += tup[u] + up[u];
	up[v] = 0;
}
int type = 1;
void solve(int n, int par) {
	ans[1] = max(ans[1], tup[n]);
	for (auto v:adj[n]) {
		if (v.ff != par) {
			ll tmp = up[v.ff];
			reroot(n, v.ff, v.ss);
			solve(v.ff, n);
			reroot(v.ff, n, tmp);
		}
	}
}

ll add = 0, addind = 0;
void getweight(int n, int par, ll cur) {
	if (cur > add) {
		addind = n;
		add = cur;
	}
	for (auto v:adj[n]) {
		if (v.ff != par) {
			getweight(v.ff, n, cur + (done[v.ff] ? 0 : v.ss));
		}
	}
}
int main() {
	io
	int n;
	cin >> n;
	ll tot = 0;
	for (int i = 0;i < n - 1;i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		tot += c + d;
		adj[a].push_back(make_pair(b, c));
		adj[b].push_back(make_pair(a, d));
	}
	int q;
	cin >> q;
	dfs(1, 0);
	solve(1, 0);
	int p1 = bind[1];
	for (int j = 1;j <= n;j++) tup[j] = 0, up[j] = 0, best[j] = 0, bind[j] = 0;
	dfs(p1, 0);
	ans[2] = tup[p1] + best[p1];
	int p2 = bind[p1], cur = p2;
	//p1 and p2 are diameter
	while (cur != p1) {
		done[cur] = 1;
		cur = par[cur];
	}

	if (n <= 2000) {
		for (int i = 3;i <= n;i++) {
			add = 0, addind = 0;
			getweight(p1, 0, 0);
			if (add == 0) {
				ans[i] = ans[i - 1];
			} else {
				ans[i] = ans[i - 1] + add;
				cur = addind;
				while (!done[cur]) {
					done[cur] = 1;
					cur = par[cur];
				}
			}
		}
	}

	for (int i = 0;i < q;i++) {
		int t;
		cin >> t;
		cout << tot - ans[t] << "\n";
	}
}
/*
4
1 2 1 2
1 3 3 4
1 4 5 6
1
2


 */

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