제출 #520877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520877		fatemetmhr	Designated Cities (JOI19_designated_cities)	C++17	23 / 100	95 ms	22624 KiB

designated_cities

//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  1e6   + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;

int n;
ll ans1 = -1;
ll ans = -1;
int ccnt = 0, den[maxn5];
bool mark[maxn5];
vector <pair<int, int>> adj[maxn5];
ll c[maxn5], best1[maxn5], up[maxn5];
int par[maxn5], ti = -1, st[maxn5], ft[maxn5], ver[maxn5];
ll edgepar[maxn5], sumall[maxn5], lazy[maxnt], out[maxn5];
ll ex[maxn5], neg[maxn5];
pair<ll, int> farr[maxn5], mx[maxnt];
pair<int, int> req[maxn5];


inline void dfsdown(int v, int par){
	best1[v] = 0;
	for(auto [u, id] : adj[v]) if(u != par){
		dfsdown(u, v);
		best1[u] += c[id];
		best1[v] += best1[u];
		ex[u] = c[id];
	}
	return;
}

inline void dfsup(int v, int par){
	ll sum = 0;
	for(auto [u, id] : adj[v]){
		if(u != par)
			sum += best1[u];
		else
			up[v] += c[id];
	}
	
	for(auto [u, id] : adj[v]) if(u != par){
		up[u] = up[v] + sum - best1[u];
		dfsup(u, v);
	}
	return;
}

inline void dfsfar1(int v, int par){
	mx[v] = {0, v};
	den[v] = v;
	for(auto [u, id] : adj[v]) if(u != par){
		dfsfar1(u, v);
		if(mx[v] <= mx[u]){
			mx[v] = mx[u];
			den[v] = u;
		}
	}
	for(auto [u, id] : adj[v]) if(u == par){
		mx[v].fi += c[id];
		neg[v] = c[id];
	}
	//cout << "so right " << v << ' ' << mx[v].fi << ' ' << mx[v].se << ' ' << den[v] << endl;
	return;
}

inline void dfsfar2(int v, int par){
	ll ex = 0;
	for(auto [u, id] : adj[v]){
		if(u != par && u != den[v]){
			farr[u] = max(farr[v], {mx[v].fi - neg[v], mx[v].se});
			farr[u].fi += c[id];
			dfsfar2(u, v);
		}
		else if(u == den[v])
			ex = c[id];
	}
	//cout << "ok " << v << ' ' << farr[v].fi << ' ' << farr[v].se << endl;
	if(den[v] == v)
		return;
	pair <ll, int> tmp = farr[v];
	for(auto [u, id] : adj[v]) if(u != par && u != den[v]){
		tmp = max(tmp, mx[u]);
	}
	farr[den[v]] = tmp;
	farr[den[v]].fi += ex;
	dfsfar2(den[v], v);

	return;
}

inline void dfs(int v, int parr){
	par[v] = parr;
	st[v] = ++ti;
	ver[ti] = v;
	for(auto [u, id] : adj[v]) if(u == parr){
		sumall[v] += c[id];
		edgepar[v] = c[id];
	}
	for(auto [u, id] : adj[v]){
		if(u != parr){
			sumall[u] += sumall[v];
			dfs(u, v);
		}
	}
	ft[v] = ti;
	return;
}

inline void build(int l, int r, int v){
	if(r - l == 1){
		mx[v].se = ver[l];
		mx[v].fi = 0;
		if(adj[ver[l]].size() == 1){
			mx[v].fi = sumall[ver[l]];
		}
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, v * 2);
	build(mid, r, v * 2 + 1);
	mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	return;
}

inline void add(int l, int r, int lq, int rq, ll val, int v){
	if(rq <= l || r <= lq)
		return;
	if(lq <= l && r <= rq){
		lazy[v] += val;
		mx[v].fi += val;
		return;
	}
	int mid = (l + r) >> 1;
	add(l, mid, lq, rq, val, v * 2);
	add(mid, r, lq, rq, val, v * 2 + 1);
	mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	mx[v].fi += lazy[v];
	return;
}

inline void cons(int v){
	if(mark[v]) 
		return;
	ans += edgepar[v];
	add(0, n, st[v], ft[v] + 1, -edgepar[v], 1);
	mark[v] = true;
	cons(par[v]);
	return;
}

inline ll find_1(){
	dfsdown(0, -1);
	dfsup(0, -1);
	ans1 = 0;
	for(int i = 0; i < n; i++){
		//cout << i << ' ' << best1[i] << ' ' << up[i] << '\n';
		best1[i] += up[i] - ex[i];
		ans1 = max(ans1, best1[i]);
		//cout << best1[i] << '\n';
	}
	//cout << "WELL " << ans1 << '\n';
	return ans1;
}

inline void find_2(){
	int r = 0;
	for(int i = 0; i < n; i++) if(adj[i].size() != 1)
		r = i;
	//cout << "rrrrrrrr " << r << endl;
	dfsfar1(r, -1);
	farr[r] = {0, 0};
	dfsfar2(r, -1);
	int optz = 0;
	for(int i = 0; i < n; i++) if(adj[i].size() == 1){
		ll val = best1[i] + farr[i].fi;
		//cout << "& " << i << ' ' << best1[i] << ' ' << farr[i].fi << ' ' << farr[i].se << endl;
		if(val >= ans){
			optz = i;
			ans = val;
		}
	}
	//cout << ans << endl;
	dfs(optz, -1);
	build(0, n, 1);
	mark[optz] = true;
	cons(farr[optz].se);
	ans -= farr[optz].fi;
	//cout << "allright " << optz << endl;
	return;
}

inline void upd(){
	if(ccnt == 0)
		return;
	int v = mx[1].se;
	cons(v);
	ccnt--;
	return;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	cin >> n;
	int ind = 0;
	ll tot = 0;
	for(int i = 0; i < n - 1; i++){
		int a, b; cin >> a >> b >> c[ind] >> c[ind + 1];
		a--; b--;
		adj[a].pb({b, ind + 1});
		adj[b].pb({a, ind});
		tot += c[ind] + c[ind + 1];
		ind += 2;
	}
	ccnt = 0;
	for(int i = 0; i < n; i++) if(adj[i].size() == 1)
		ccnt++;
	int q; cin >> q;
	for(int i = 0; i < q; i++){
		cin >> req[i].fi;
		req[i].se = i;
	}
	if(n == 2){
		for(int i = 0; i < q; i++){
			if(req[i].fi == 1){
				cout << min(c[0], c[1]) << '\n';
			}
			else{
				cout << 0 << '\n';
			}
		}
		return 0;
	}
	sort(req, req + q);
	find_1();
	find_2();
	int last = 2;
	//cout << ans << endl;
	for(int i = 0; i < q; i++){
		if(req[i].fi == 1){
			out[req[i].se] = ans1;
			//cout << "well done " << i << ' ' << req[i].se << ' ' << out[req[i].se] << ' ' << ans1 << '\n';
		}
		else{
			while(last < req[i].fi){
				last++;
				upd();
			}
			out[req[i].se] = ans;
		}
	}
	for(int i = 0; i < q; i++)
		cout << tot - out[i] << '\n';
}

/*
5
2 1 5 5
3 2 4 5
4 2 4 3
5 4 5 5
1
2
*/

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