#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
using namespace std;
const int Nmax = 2e5 + 5;
typedef long long ll;
struct edge
{
int to, toy, fromy;
};
vector<edge> v[Nmax];
ll ans[Nmax];
int n;
namespace special_case_for_one
{
static ll dfs(int node, int dad = 0)
{
ll sum = 0;
for(auto it : v[node])
if(it.to != dad)
sum += it.fromy + dfs(it.to, node);
return sum;
}
static ll get_best(int node, int dad, ll now)
{
ll best = now;
for(auto it : v[node])
if(it.to != dad)
best = max(best, get_best(it.to, node, now + it.toy - it.fromy));
return best;
}
static ll solve1()
{
return get_best(1, 0, dfs(1));
}
}
namespace special_case
{
int root;
ll best2 = 0;
static pair<ll, int> best[Nmax];
static int w[Nmax], subarb[Nmax];
static ll c[Nmax];
static bool used[Nmax];
static int S;
static void dfs0(int node, int dad = 0)
{
w[node] = 1;
for(auto it : v[node])
if(it.to != dad && !used[it.to])
{
dfs0(it.to, node);
w[node] += w[it.to];
}
}
static pair<int,int> centroid(int node, int dad = 0)
{
int act = S - w[node];
pair<int,int> best = {S, -1};
for(auto it : v[node])
if(it.to != dad && !used[it.to])
{
best = min(best, centroid(it.to, node));
act = max(act, w[it.to]);
}
best = min(best, {act, node});
return best;
}
static ll dfs(int node, int dad = 0)
{
ll sum = 0;
if(dad)
{
if(w[dad] == -1) subarb[node] = node;
else subarb[node] = subarb[dad];
best[subarb[node]] = max(best[subarb[node]], {c[node], node});
}
for(auto it : v[node])
if(it.to != dad && !used[it.to])
{
c[it.to] = c[node] + it.toy;
sum += it.fromy + dfs(it.to, node);
}
return sum;
}
static void solve2(int node)
{
dfs0(node);
S = w[node];
node = centroid(node).second;
c[node] = 0;
w[node] = -1;
for(auto it : v[node])
if(!used[it.to])
best[it.to] = {-1, -1};
ll sum = dfs(node);
vector< pair<ll,int> > now;
for(auto it : v[node])
if(!used[it.to])
now.push_back(best[it.to]);
if(now.size() >= 2)
{
nth_element(now.begin(), now.end() - 2, now.end());
ll W = sum + now[now.size()-2].first + now[now.size()-1].first;
if(W > best2)
{
best2 = W;
root = now.back().second;
}
}
else
if(now.size() >= 1)
{
ll W = sum + now[0].first;
if(W > best2)
{
best2 = W;
root = node;
}
}
used[node] = 1;
for(auto it : v[node])
if(!used[it.to]) solve2(it.to);
}
}
static pair<ll, int> operator + (pair<ll, int> a, ll b)
{
a.first += b;
return a;
}
#define mid ((st+dr)>>1)
#define left_son ((node<<1))
#define right_son ((node<<1)|1)
namespace SegTree
{
int n;
vector<pair<ll, int>> a;
vector<ll> lazy;
static void up(int x){
while(x /= 2)
a[x] = max(a[2 * x], a[2 * x + 1]) + lazy[x];
}
static void add_lazy(int x, int delta){
a[x].first += delta;
lazy[x] += delta;
}
static void update(int st, int dr, int delta)
{
const int st0 = --st, dr0 = --dr;
for(st += n, dr += n + 1; st < dr; st /= 2, dr /= 2){
if(st % 2) add_lazy(st++, delta);
if(dr % 2) add_lazy(--dr, delta);
}
up(st0);
up(dr0);
}
static void build(int N, ll *which)
{
n = N;
a.resize(2 * n);
lazy.resize(n);
for(int i = 0; i < n; ++i)
a[i + n] = make_pair(which[i + 1], i + 1);
for(int i = n - 1; i > 0; --i)
a[i] = max(a[2 * i], a[2 * i + 1]);
}
static pair<ll, int> query()
{
return a[1];
}
};
namespace solve_for_all
{
static int up[Nmax];
static ll up_chain[Nmax];
static int tmp, in[Nmax], out[Nmax], t[Nmax];
static bool used[Nmax];
static ll which[Nmax];
static int ord[Nmax];
static ll dfs(int node, int dad = 0)
{
t[node] = dad;
in[node] = ++tmp;
ll sum = 0;
for(auto it : v[node])
if(it.to != dad)
{
up[it.to] = it.toy;
up_chain[it.to] = up[it.to] + up_chain[node];
sum += it.fromy + dfs(it.to, node);
}
out[node] = tmp;
return sum;
}
static void solve(int node)
{
memset(used, 0, sizeof(used));
tmp = 0;
up_chain[node] = up[node] = 0;
ll Ans = dfs(node);
int i;
for(i=1; i<=n; ++i) ord[in[i]] = i;
for(i=1; i<=n; ++i) which[i] = up_chain[ord[i]];
SegTree::build(n, which);
used[node] = 1;
for(i=2; i<=n; ++i)
{
auto res = SegTree::query();
if(!res.first) break;
Ans += res.first;
ans[i] = max(ans[i], Ans);
int x = ord[res.second];
while(!used[x])
{
SegTree::update(in[x], out[x], -up[x]);
used[x] = 1;
x = t[x];
}
}
for(; i<=n; ++i) ans[i] = max(ans[i], Ans);
}
}
const int sz = 1e6;
char buf[sz+40];
int main()
{
cin.rdbuf()->pubsetbuf(buf, sz);
// freopen("input", "r", stdin);
cin.sync_with_stdio(false);
cin.tie(0);
ll sum = 0;
int i;
cin >> n;
for(i=1; i<n; ++i)
{
int x, y, c1, c2;
cin >> x >> y >> c1 >> c2;
v[x].push_back({y, c1, c2});
v[y].push_back({x, c2, c1});
sum += c1 + c2;
}
ans[1] = special_case_for_one :: solve1();
special_case :: solve2(1);
solve_for_all :: solve(special_case :: root);
// for(i=1; i<=n; ++i)
// solve_for_all :: solve(i);
int q;
cin >> q;
while(q--)
{
int x;
cin >> x;
cout << sum - ans[x] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
10752 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
10624 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
10512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
10752 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
10624 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
10752 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
