#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) cout << "[" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "]\n"
#define rd() abs((int)rng())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, int>pii;
const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, q, tin[maxn], tout[maxn], tim, vert[maxn], par[maxn];
vector<pii>adj[maxn];
ll up, sum[maxn], ans[maxn], tot;
void dfs(int v, ll csum = 0)
{
tin[v] = ++tim;
for(pii to : adj[v])
{
if(to.x == par[v])
up += to.y;
else
{
par[to.x] = v;
dfs(to.x, csum + to.y);
}
}
tout[v] = tim;
if(tin[v] == tout[v])
{
sum[tin[v]] = csum;
vert[tin[v]] = v;
}
}
pii seg[maxn * 4];
ll lazy[maxn * 4];
void build(int id = 1, int l = 1, int r = tim)
{
if(l == r)
{
seg[id] = {sum[l], vert[l]};
return;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}
void upd(int id, ll val)
{
seg[id].x += val;
lazy[id] += val;
}
void shift(int id)
{
if(!lazy[id]) return;
upd(id * 2, lazy[id]);
upd(id * 2 + 1, lazy[id]);
lazy[id] = 0;
}
void modify(int x, int y, ll val, int id = 1, int l = 1, int r = tim)
{
if(l > y || r < x) return;
if(l >= x && r <= y)
{
upd(id, val);
return;
}
shift(id);
int mid = (l + r) / 2;
modify(x, y, val, id * 2, l, mid);
modify(x, y, val, id * 2 + 1, mid + 1, r);
seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}
map<int, int>edge[maxn];
int main()
{
ios_base::sync_with_stdio(false), cin.tie(0);
cin >> n;
for(int i = 0; i < n - 1; i++)
{
int a, b;
ll c, d;
cin >> a >> b >> c >> d;
tot += c + d;
adj[a].pb({b, c});
adj[b].pb({a, d});
edge[a][b] = c;
edge[b][a] = d;
}
dfs(1);
build();
ll cur_ans = 0;
for(int i = 1; i <= tim; i++)
{
pii best = seg[1];
cur_ans += best.x;
if(i >= 2)
ans[i] = tot - (up + cur_ans);
int v = best.y;
while(edge[v].count(par[v]))
{
modify(tin[v], tout[v], -edge[v][par[v]]);
edge[v].erase(edge[v].find(par[v]));
v = par[v];
}
}
cin >> q;
for(int i = 0; i < q; i++)
{
int c; cin >> c;
cout << ans[c] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
