제출 #376205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376205		8e7	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	717 ms	50932 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], wei[maxn];
int par[maxn];
bool done[maxn];

int lef[maxn], rig[maxn], arr[maxn];
int ord = 0;
void dfs(int n, int pa) {
	arr[ord] = n;
	lef[n] = ord++;
	par[n] = pa;
	for (auto v:adj[n]) {
		if (v.ff != pa) {
			wei[v.ff] = v.ss;
			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;
		}
	}
	rig[n] = ord;
}
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));
		}
	}
}

ll seg[4 * maxn], tag[4 * maxn];
void modify(int cur, int l, int r, int ql, int qr, ll val) {
	if (r <= l || ql >= r || qr <= l) return;
	if (ql <= l && qr >= r) {
		tag[cur] += val;
		return;
	}
	int mid = (l + r) / 2;
	modify(cur * 2, l, mid, ql, qr, val);
	modify(cur * 2 + 1, mid, r, ql, qr, val);
	seg[cur] = max(seg[cur * 2] + tag[cur * 2], seg[cur * 2 + 1] + tag[cur * 2 + 1]);
}
pii query(int cur, int l, int r) {
	if (r <= l) return make_pair(0, 0);
	if (r - l == 1) return make_pair(l, seg[cur] + tag[cur]);
	int mid = (l + r) / 2;
	if (seg[cur * 2] + tag[cur * 2] > seg[cur * 2 + 1] + tag[cur * 2 + 1]) {
		pii ret = query(cur * 2, l, mid);
		ret.ss += tag[cur];
		return ret;
	} else {
		pii ret = query(cur * 2 + 1, mid, r);
		ret.ss += tag[cur];
		return ret;
	}
}

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, wei[j] = 0;

	ord = 0;
	dfs(p1, 0);
	ans[2] = tup[p1] + best[p1];
	int p2 = bind[p1], cur = p2;
	//p1 and p2 are diameter
	//cout << p1 <<" " << p2 << endl;
	//for (int i = 0;i < n;i++) cout << arr[i] << " " << wei[arr[i]] << endl;
	//cout << endl;
	for (int i = 1;i <= n;i++) {
		//cout << lef[i] << " " << rig[i] << " " << wei[i] << endl;
		modify(1, 0, n, lef[i], rig[i], wei[i]);
	}
	while (cur != p1) {
		done[cur] = 1;
		//cout << lef[cur] << " " << rig[cur] << " " << -wei[cur] << endl;
		modify(1, 0, n, lef[cur], rig[cur], -wei[cur]);
		cur = par[cur];
	}
	for (int i = 3;i <= n;i++) {
		pii leaf = query(1, 0, n);
		leaf.ff = arr[leaf.ff];
		//getweight(p1, 0, 0);
		if (leaf.ss == 0) {
			ans[i] = ans[i - 1];
		} else {
			ans[i] = ans[i - 1] + leaf.ss;
			cur = leaf.ff;
			while (!done[cur]) {
				done[cur] = 1;
				//cout << lef[cur] << " " << rig[cur] << " " << -wei[cur] << endl;
				modify(1, 0, n, lef[cur], rig[cur], -wei[cur]);
				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

15
14 5 12 7
14 12 6 5
14 10 14 16
9 14 16 12
13 7 4 15
1 3 8 1
6 7 15 13
15 4 4 6
9 1 12 6
13 1 7 6
13 4 5 15
2 6 11 19
8 4 12 7
13 11 14 5
3
3
6
7

 */

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