Submission #376244

#	Time	Username	Problem	Language	Result	Execution time	Memory
376244		Kevin_Zhang_TW	Designated Cities (JOI19_designated_cities)	C++17	16 / 100	358 ms	43244 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 200010;
const ll inf = 1ll << 59;

int n, q;
ll dprt[MAX_N], dpson[MAX_N], res[MAX_N], allsum;
vector<pair<int,int>> edge[MAX_N];

ll dfs1(int x, int lst = -1) {
	ll uplen = 0;
	for (auto [u, w] : edge[x]) if (u != lst) 
		dpson[x] += dfs1(u, x);
	else uplen = w;
	return dpson[x] + uplen;
}

void dfs2(int x, int lst = -1, ll upson = 0) {
	if (lst == -1) dprt[x] = dpson[x];
	dprt[x] += upson;
	for (auto [u, w] : edge[x]) if (u == lst)
		dprt[x] -= w;
	for (auto [u, w] : edge[x]) if (u != lst)
		dfs2(u, x, dprt[x] + w);
}

pair<int,int> best[MAX_N];
ll bstsum[MAX_N];

pair<ll,ll> mxlen[MAX_N];

void dfs3(int x, int lst = -1) {
	mxlen[x] = {0, x};
	for (auto [u, w] : edge[x]) if (u != lst) {
		dfs3(u, x);
		if (chmax(bstsum[x], bstsum[u]))
			best[x] = best[u];
		mxlen[u].first += w;

		if (chmax(bstsum[x], 
					mxlen[x].first + mxlen[u].first + dprt[x]))
			best[x] = {mxlen[x].second, mxlen[u].second};
		chmax(mxlen[x], mxlen[u]);
	}
}
void solve() {
	dfs3(1);
	res[2] = bstsum[1];
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int a, b, c, d, i = 1;i < n;++i) {
		cin >> a >> b >> c >> d;
		edge[a].pb(b, c);
		edge[b].pb(a, d);
		allsum += c + d;
	}

	dfs1(1);
	dfs2(1);

	res[1] = *max_element(dprt+1, dprt+1+n);

	solve();

	cin >> q;

	for (int i = 0, v;i < q;++i) {
		cin >> v;
		cout << allsum - res[v] << '\n';
	}
}

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