This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
template<typename T>
bool minimize(T& a, const T& b){
if(a > b){
return a = b, true;
}
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b){
return a = b, true;
}
return false;
}
using ll = long long;
using ld = long double;
using ull = unsigned long long;
const ll inf = 1e18;
struct SegmentTree{
vector<ll> lazy;
vector<pair<ll, int>> st;
SegmentTree(int n) : lazy(n << 2, 0), st(n << 2, make_pair(0, 0)) {}
void build(int id, int l, int r){
if(l == r){
st[id] = {0, l};
} else{
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
}
void apply(int id, long long val){
st[id].first += val;
lazy[id] += val;
}
void lazyDown(int id){
apply(id << 1, lazy[id]);
apply(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, long long val){
if(u <= l && r <= v) apply(id, val);
else{
int mid = l + r >> 1;
lazyDown(id);
if(u <= mid) update(id << 1, l, mid, u, v, val);
if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
}
pair<ll, int> query(){
return st[1];
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
#endif // LOCAL
int N;
cin >> N;
vector<vector<tuple<int, int, int>>> adj(N);
for(int i = 0; i < N - 1; ++i){
int u, v, c, d;
cin >> u >> v >> c >> d;
--u, --v;
adj[u].emplace_back(v, c, d);
adj[v].emplace_back(u, d, c);
}
vector<ll> f(N), g(N), up(N), down(N);
function<void(int, int)> dfs = [&](int u, int p){
for(auto [v, c, d] : adj[u]) if(v != p){
down[v] = down[u] + c;
up[v] = up[u] + d;
dfs(v, u);
f[u] += f[v] + c;
}
};
dfs(0, -1);
g[0] = f[0];
function<void(int, int)> reroot_dfs = [&](int u, int p){
for(auto [v, c, d] : adj[u]) if(v != p){
g[v] = g[u] - c + d;
reroot_dfs(v, u);
}
};
reroot_dfs(0, -1);
vector<long long> answer(N + 1, LLONG_MAX);
for(int i = 0; i < N; ++i){
minimize(answer[1], g[i]);
}
vector<pair<long long, int>> lowest(N, {-inf, -1});
tuple<long long, int, int> solution_for_two_leaves = {inf, -1, -1};
for(int u = 0; u < N; ++u){
if((int)adj[u].size() == 1){
lowest[u] = {down[u], u};
}
}
function<void(int, int)> dfs_dp = [&](int u, int p){
pair<long long, int> A = lowest[u], B = {-inf, -1};
for(auto [v, c, d] : adj[u]) if(v != p){
dfs_dp(v, u);
if(A < lowest[v]){
B = A;
A = lowest[v];
} else maximize(B, lowest[v]);
maximize(lowest[u], lowest[v]);
}
if(B.first != -inf){
long long delta = 2 * down[u] - A.first - B.first + up[u] - down[u];
int u = A.second, v = B.second;
minimize(solution_for_two_leaves, make_tuple(delta, u, v));
}
};
dfs_dp(0, -1);
long long delta;
int l1, l2;
tie(delta, l1, l2) = solution_for_two_leaves;
answer[2] = f[0] + delta;
vector<int> parent(N), down_e(N), tin(N), tout(N), tour(N);
int timer_dfs = 0;
function<void(int, int)> re_dfs = [&](int u, int p){
tour[tin[u] = timer_dfs++] = u;
for(auto [v, c, d] : adj[u]) if(v != p){
parent[v] = u;
down_e[v] = c;
re_dfs(v, u);
}
tout[u] = timer_dfs - 1;
};
re_dfs(l1, -1);
SegmentTree T(N);
T.build(1, 0, N - 1);
for(int i = 0; i < N; ++i) if(i != l1){
T.update(1, 0, N - 1, tin[i], tout[i], down_e[i]);
}
vector<bool> used(N, false);
used[l1] = true;
auto pave = [&](int u) -> void{
while(!used[u]){
used[u] = true;
T.update(1, 0, N - 1, tin[u], tout[u], -down_e[u]);
T.update(1, 0, N - 1, tin[u], tin[u], -inf);
u = parent[u];
}
};
pave(l2);
bool process = true;
for(int i = 3; i <= N; ++i){
answer[i] = answer[i - 1];
if(process){
pair<ll, int> cur = T.query();
if(cur.first > 0){
answer[i] -= cur.first;
int u = tour[cur.second];
pave(u);
} else{
process = false;
}
}
}
int Q;
cin >> Q;
while(Q--){
int k;
cin >> k;
cout << answer[k] << '\n';
}
return 0;
}
Compilation message (stderr)
designated_cities.cpp: In member function 'void SegmentTree::build(int, int, int)':
designated_cities.cpp:40:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int mid = l + r >> 1;
| ~~^~~
designated_cities.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, long long int)':
designated_cities.cpp:61:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid = l + r >> 1;
| ~~^~~
designated_cities.cpp: In lambda function:
designated_cities.cpp:97:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
97 | for(auto [v, c, d] : adj[u]) if(v != p){
| ^
designated_cities.cpp: In lambda function:
designated_cities.cpp:109:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
109 | for(auto [v, c, d] : adj[u]) if(v != p){
| ^
designated_cities.cpp: In lambda function:
designated_cities.cpp:134:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
134 | for(auto [v, c, d] : adj[u]) if(v != p){
| ^
designated_cities.cpp: In lambda function:
designated_cities.cpp:165:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
165 | for(auto [v, c, d] : adj[u]) if(v != p){
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |