#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;
if (d == root)
return root;
return par[d];
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]);
//cout << "range " << left << " " << right << " " << tree[root].pos << " " << tree[root].mx << endl;
}
void push_lazy(int root, int left, int right)
{
if (lazy[root] != 0)
///cout << "apply lazy " << root << " " << left << " " << right << " " << lazy[root] << endl;
tree[root].mx += lazy[root];
if (left != right)
{
lazy[root * 2] += lazy[root];
lazy[root * 2 + 1] += lazy[root];
}
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)
{
//cout << "update range " << left << " " << right << " " << val << endl;
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]);
}
int get(int root, int left, int right, int pos)
{
push_lazy(root, left, right);
///cout << "get " << root << " " << left << " " << right << " " << tree[root].mx << " " << tree[root].pos << endl;
if (left == right)
return tree[root].mx;
int mid = (left + right) / 2;
if (pos <= mid)
return get(root * 2, left, mid, pos);
return get(root * 2 + 1, mid + 1, right, pos);
}
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];
///cout << "root " << root << endl;
build(1, 1, n);
while(true)
{
node cur = tree[1];
int d = cur.pos;
// cout << cur.pos << " : " << cur.mx << endl;
/**for (int i = 1; i <= n; i ++)
if (depth[i] > depth[d])
d = i;*/
///cout << "real " << d << " " << depth[d] << " to " << get(1, 1, n, tin[11]) << endl;
if (depth[d] == 0)
break;
pivot ++;
so_far -= cur.mx;
///so_far -= depth[d];
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 |
10 ms |
33756 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
33628 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
33628 KB |
Output is correct |
| 2 |
Correct |
318 ms |
45500 KB |
Output is correct |
| 3 |
Correct |
482 ms |
66060 KB |
Output is correct |
| 4 |
Correct |
306 ms |
50288 KB |
Output is correct |
| 5 |
Correct |
337 ms |
51652 KB |
Output is correct |
| 6 |
Correct |
345 ms |
53576 KB |
Output is correct |
| 7 |
Correct |
297 ms |
51740 KB |
Output is correct |
| 8 |
Correct |
429 ms |
65616 KB |
Output is correct |
| 9 |
Correct |
229 ms |
52336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
33628 KB |
Output is correct |
| 2 |
Incorrect |
317 ms |
45336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
33756 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
33628 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
33628 KB |
Output is correct |
| 2 |
Correct |
318 ms |
45500 KB |
Output is correct |
| 3 |
Correct |
482 ms |
66060 KB |
Output is correct |
| 4 |
Correct |
306 ms |
50288 KB |
Output is correct |
| 5 |
Correct |
337 ms |
51652 KB |
Output is correct |
| 6 |
Correct |
345 ms |
53576 KB |
Output is correct |
| 7 |
Correct |
297 ms |
51740 KB |
Output is correct |
| 8 |
Correct |
429 ms |
65616 KB |
Output is correct |
| 9 |
Correct |
229 ms |
52336 KB |
Output is correct |
| 10 |
Correct |
6 ms |
33628 KB |
Output is correct |
| 11 |
Incorrect |
317 ms |
45336 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
33756 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
33628 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
