#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
const int maxn = 2e5 + 12;
int n, cst[2*maxn];
ll edgesum = 0;
vector<array<int, 2>> g[maxn];
ll sub[maxn];
void sub_cost(int v, int p) {
sub[v] = 0;
for(auto [i, id] : g[v]) if(i != p) {
sub_cost(i, v);
sub[v] += sub[i] + cst[id];
}
}
ll arb[maxn];
void reroot_cost(int v, int p, ll sum) {
arb[v] = sum;
for(auto [i, id] : g[v]) if(i!=p) {
reroot_cost(i, v, sum-cst[id]+cst[id^1]);
}
}
ll greedy[maxn], used[maxn];
array<ll, 2> find_leaf(int v, int p) {
array<ll, 2> ans = {0, v};
for(auto [i, id] : g[v]) if(i != p) {
auto t = find_leaf(i, v);
//cout << t[0]+( cst[id^1]*!used[id^1]) << endl;
t[0] += cst[id^1]*!used[id^1];
ans = max(ans, t);
}
return ans;
}
array<ll, 2> far[maxn];
void sub_far(int v, int p) {
far[v] = {0, -(1ll<<56)};
for(auto &[i, id] : g[v]) if(i != p) {
sub_far(i, v);
auto t = far[i];
t[0] += cst[id^1];
t[1] += cst[id^1];
if(far[v][0] < t[0])
swap(far[v][0], t[0]);
far[v][1] = max(far[v][1], t[0]);
}
}
ll F[maxn];
void reroot_far(int v, int p, ll over) {
F[v] = max(far[v][0], over);
//cout << v << " -- " << F[v] << endl;
for(auto [i, id] : g[v]) if(i != p) {
reroot_far(i, v, cst[id]+max(over, far[i][0]+cst[id^1] == far[v][0] ? far[v][1] : far[v][0]));
}
}
ll solFor2 = 0;
int solve2() {
sub_far(1, 0);
reroot_far(1, 0, -(1ll<<60));
array<ll, 2> sol = {-(1ll<<60), -1};
for(int i = 1; i <= n; i++)
sol = max(sol, {F[i]+arb[i], i});
//cout << edgesum << " ? " << sol[0] << " " << sol[1] << endl;
//cout << arb[3] << " " << arb[4] << endl;
//cout << sol[0] << "/ " << edgesum << endl;
solFor2 = edgesum - sol[0];
return sol[1];
}
int par[maxn], par_edge[maxn], tin[maxn], tout[maxn], timer = 1;
int tinToV[maxn];
vector<ll> dep;
void find_pars(int v, int p, ll d) {
tin[v] = timer++;
dep[tin[v]] = d;
tinToV[tin[v]] = v;
for(auto [i, id] : g[v]) if(i != p) {
par[i] = v;
par_edge[i] = id^1;
find_pars(i, v, d + cst[id^1]);
}
tout[v] = timer-1;
}
struct SegTree {
struct Node {
array<ll, 2> val;
ll lazy;
Node(ll x = 0) : val{x, 0}, lazy(0) {}
Node(array<ll, 2> x) : val{x[0], x[1]}, lazy(0) {}
void apply(ll x) {
lazy += x;
val[0] += x;
}
void push(Node &l, Node &r) {
l.apply(lazy), r.apply(lazy);
lazy = 0;
}
friend Node operator+(const Node &a, const Node &b) {
return Node(max(a.val, b.val));
}
};
int n;
vector<Node> tree;
SegTree(int n) : n(n), tree(4*n) {}
void build(int v, int l, int r, vector<ll> &dep) {
if(l == r) {
tree[v].val = {dep[l], l};
return;
}
int mid = (l+r)/2;
build(2*v, l, mid, dep);
build(2*v+1, mid+1, r, dep);
tree[v] = tree[2*v]+tree[2*v+1];
}
void build(vector<ll> &dep) {
build(1, 1, n, dep);
}
void update(int v, int l, int r, int ql, int qr, ll add) {
if(r < ql || qr < l) return;
if(ql <= l && r <= qr) {
tree[v].apply(add);
return;
}
int mid = (l+r)/2;
tree[v].push(tree[2*v], tree[2*v+1]);
update(2*v, l, mid, ql, qr, add);
update(2*v+1, mid+1, r, ql, qr, add);
tree[v] = tree[2*v]+tree[2*v+1];
}
void update(int ql, int qr, ll add) {
update(1, 1, n, ql, qr, add);
}
Node query(int v, int l, int r, int ql, int qr) {
if(r < ql || qr < l) return Node();
if(ql <= l && r <= qr) return tree[v];
int mid = (l+r)/2;
tree[v].push(tree[2*v], tree[2*v+1]);
return query(2*v, l, mid, ql, qr) + query(2*v+1, mid+1, r, ql, qr);
}
array<ll, 2> query(int ql, int qr) {
return query(1, 1, n, ql, qr).val;
}
};
void solve(int v) {
for(int i = 0; i < 2*n; i++) used[i] = 0;
dep.resize(n+1);
find_pars(v, 0, 0);
sub_cost(v, 0);
ll cur = sub[v];
SegTree st(n);
st.build(dep);
//for(int i = 1; i <= n; i++)
// cout << st.query(tin[i], tin[i])[0] << " vs " << dep[i] << endl;
//cout << '\n';
for(int i = 2; i <= n; i++) {
auto [add, x] = st.query(1, n);
cur += add;
x = tinToV[x];
greedy[i] = edgesum - cur;
for(; x != v && !used[par_edge[x]]; x = par[x]) {
st.update(tin[x], tout[x], -cst[par_edge[x]]);
used[par_edge[x]] = 1;
}
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int f, t, x, y, i = 1; i < n; i++) {
cin >> f >> t >> cst[2*i-1] >> cst[2*i-2];
edgesum += cst[2*i-1];
edgesum += cst[2*i-2];
g[f].push_back({t, 2*i-2});
g[t].push_back({f, 2*i-1});
}
sub_cost(1, 0);
reroot_cost(1, 0, sub[1]);
//for(int i = 1; i <= n; i++) cout << arb[i] << " "; cout << endl;
auto point = solve2();
memset(greedy, 0x4f, sizeof greedy);
solve(point);
int q;
cin >> q;
greedy[1] = edgesum-*max_element(arb+1, arb+n+1);
//greedy[2] = solFor2;
for(int t; q--;) {
cin >> t;
cout << greedy[t] << '\n';
}
}
Compilation message
timeleap.cpp: In function 'int main()':
timeleap.cpp:175:19: warning: unused variable 'x' [-Wunused-variable]
175 | for(int f, t, x, y, i = 1; i < n; i++) {
| ^
timeleap.cpp:175:22: warning: unused variable 'y' [-Wunused-variable]
175 | for(int f, t, x, y, i = 1; i < n; i++) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
9964 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
10092 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
9964 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
