Submission #376162

#	Time	Username	Problem	Language	Result	Execution time	Memory
376162		8e7	Designated Cities (JOI19_designated_cities)	C++14	16 / 100	610 ms	62956 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];
multiset<ll> mdown[maxn];
void dfs(int n, int par) {
	for (auto v:adj[n]) {
		if (v.ff != par) {
			dfs(v.ff, n);
			tup[n] += tup[v.ff] + up[v.ff];
			best[n] = max(best[n], v.ss + best[v.ff]);
			mdown[n].insert(v.ss + best[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];

	mdown[u].erase(mdown[u].find(w + best[v]));
	best[u] = (mdown[u].size() ? *prev(mdown[u].end()) : 0);
	mdown[v].insert(best[u] + up[v]);
	best[v] = max(best[v], best[u] + up[v]);
	up[v] = 0;
}
int type = 1;
ll ans = 0;
void solve(int n, int par) {
	ans = max(ans, tup[n] + (type == 1 ? 0 : best[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);
		}
	}
}
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;
	for (int i = 0;i < q;i++) {
		int t;
		cin >> t;
		type = t;
		dfs(1, 0);
		solve(1, 0);
		cout << tot - ans << '\n';
	}
}
/*
4
1 2 1 2
1 3 3 4
1 4 5 6
1
2
 */

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