#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 2e5 + 10;
struct edge
{
int v, u;
ll c, d;
edge(int _v = 0, int _u = 0, ll _c = 0, ll _d = 0)
{
v = _v;
u = _u;
c = _c;
d = _d;
}
} edges[maxn];
int n;
vector < pair < int, int > > adj[maxn];
ll sum_all = 0;
void input()
{
cin >> n;
for (int i = 1; i < n; i ++)
{
cin >> edges[i].v >> edges[i].u >> edges[i].c >> edges[i].d;
adj[edges[i].v].push_back({edges[i].u, i});
adj[edges[i].u].push_back({edges[i].v, i});
sum_all += edges[i].c + edges[i].d;
}
}
const ll inf = 1e18;
ll single;
ll sub[maxn];
void calc(int v, int p)
{
sub[v] = 0;
for (pair < int, int > nb : adj[v])
{
int u = nb.first;
if (u == p)
continue;
calc(u, v);
if (v == edges[nb.second].v)
sub[v] += edges[nb.second].d; //cout << "edge " << v << " : " << u << " : " << edges[nb.second].d << endl;
else
sub[v] += edges[nb.second].c;
sub[v] += sub[u];
}
//cout << "calc " << v << " " << sub[v] << endl;
}
void single_dfs(int v, int p, ll val)
{
single = max(single, val);
///cout << v << " : " << val << endl;
for (pair < int, int > nb : adj[v])
{
int u = nb.first;
if (u == p)
continue;
ll cur;
if (v == edges[nb.second].v)
cur = edges[nb.second].c - edges[nb.second].d;
else
cur = edges[nb.second].d - edges[nb.second].c;
single_dfs(u, v, val + cur);
}
}
void solve_single()
{
calc(1, -1);
single_dfs(1, -1, sub[1]);
single = sum_all - single;
}
ll depth[maxn];
int ord[maxn], timer;
int tin[maxn], tout[maxn];
int par[maxn], ridx[maxn], marked[maxn];
void do_math(int v, int p, int id)
{
par[v] = p;
ridx[v] = id;
ord[++ timer] = v;
tin[v] = timer;
for (pair < int, int > nb : adj[v])
{
int u = nb.first, idx = nb.second;
if (u == p)
continue;
ll val;
if (v == edges[idx].v)
val = edges[idx].c;
else
val = edges[idx].d;
if (marked[idx])
val = 0;
depth[u] = depth[v] + val;
do_math(u, v, idx);
}
tout[v] = timer;
}
bool in_subtree(int v, int u)
{
return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
void go_mark(int v)
{
while(par[v] != -1)
{
marked[ridx[v]] = 1;
v = par[v];
}
}
int find_root()
{
int root = 1;
while(true)
{
timer = 0;
depth[root] = 0;
for (int i = 1; i <= n; i ++)
marked[i] = 0;
do_math(root, - 1, - 1);
int d = 1;
for (int i = 1; i <= n; i ++)
if (depth[i] > depth[d])
d = i;
go_mark(d);
timer = 0;
depth[root] = 0;
do_math(root, - 1, - 1);
int f = 1;
for (int i = 1; i <= n; i ++)
if (depth[i] > depth[f])
f = i;
bool done = true;
for (pair < int, int > nb : adj[root])
{
int u = nb.first;
if (in_subtree(u, d) && in_subtree(u, f))
{
done = false;
root = u;
break;
}
}
if (done)
break;
}
return root;
}
ll values[maxn];
struct node
{
ll mx;
int pos;
node (int _pos = 0, ll _mx = 0)
{
pos = _pos;
mx = _mx;
}
};
node unite(node lf, node rf)
{
if (lf.mx > rf.mx)
return lf;
return rf;
}
node tree[4 * maxn];
ll lazy[4 * maxn];
void build(int root, int left, int right)
{
if (left == right)
{
tree[root] = node(ord[left], depth[ord[left]]);
return;
}
int mid = (left + right) / 2;
build(root * 2, left, mid);
build(root * 2 + 1, mid + 1, right);
tree[root] = unite(tree[root * 2], tree[root * 2 + 1]);
}
void push_lazy(int root, int left, int right)
{
tree[root].mx += lazy[root];
if (left != right)
{
lazy[root * 2] += lazy[root];
lazy[root * 2 + 1] += lazy[root];
return;
}
lazy[root] = 0;
}
void update(int root, int left, int right, int qleft, int qright, ll val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root] = val;
push_lazy(root,left, right);
return;
}
int mid = (left + right) / 2;
update(root * 2, left, mid, qleft, qright, val);
update(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = unite(tree[root * 2], tree[root * 2 + 1]);
}
void clean(int v)
{
while(par[v] != -1)
{
if (marked[ridx[v]])
break;
marked[ridx[v]] = 1;
ll cur;
if (edges[ridx[v]].u == v)
cur = edges[ridx[v]].c;
else
cur = edges[ridx[v]].d;
update(1, 1, n, tin[v], tout[v], - cur);
//for (int i = tin[v]; i <= tout[v]; i ++)
// depth[ord[i]] -= cur;
v = par[v];
}
}
void simulate(int root)
{
calc(root, -1);
timer = 0;
depth[root] = 0;
for (int i = 1; i <= n; i ++)
marked[i] = 0;
do_math(root, - 1, - 1);
int pivot = 0;
ll so_far = sum_all - sub[root];
build(1, 1, n);
while(true)
{
node cur = tree[1];
int d = cur.pos;
/**int d = 1;
for (int i = 1; i <= n; i ++)
if (depth[i] > depth[d])
d = i;*/
if (cur.mx == 0)
break;
pivot ++;
so_far -= cur.mx;
clean(d);
values[pivot] = so_far;
}
int q;
cin >> q;
for (int i = 1; i <= q; i ++)
{
int e;
cin >> e;
if (e == 1)
{
cout << single << endl;
continue;
}
if (e > pivot)
e = pivot;
cout << values[e] << endl;
}
}
void solve()
{
input();
solve_single();
int root = find_root();
simulate(root);
}
int main()
{
speed();
int t = 1;
///cin >> t;
while(t --)
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
22360 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
22364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
22364 KB |
Output is correct |
| 2 |
Execution timed out |
2065 ms |
40788 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
22360 KB |
Output is correct |
| 2 |
Execution timed out |
2050 ms |
40660 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
22360 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
22364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
22364 KB |
Output is correct |
| 2 |
Execution timed out |
2065 ms |
40788 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
22360 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
22364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
