#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define all(s) s.begin(), s.end()
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define pi pair < int, int >
const int N = 2e5 + 7;
const int INF = 1e9 + 7;
pi t[4 * N];
int lz[4 * N];
int p[N][20], h[2][N], w[N];
int tin[N], tout[N], tim;
int ans[N];
int n, rt, s, s_up;
vector < pair < int, pi > > g[N];
pi lr[N], lg[2][N];
int rv[N], del[N], cnt;
vector < int > a;
int lc, x, y;
void dfs (int v, int pr = 0){
lg[0][v] = lg[1][v] = {0, v};
lr[v] = {INF, 0};
tin[v] = ++tim;
p[v][0] = pr;
for (int j = 1; j < 20; j++)
p[v][j] = p[p[v][j - 1]][j - 1];
for (auto to : g[v]){
if (to.fr != pr){
s_up += to.sc.sc;
h[0][to.fr] = h[0][v] + to.sc.fr;
h[1][to.fr] = h[1][v] + to.sc.sc;
dfs(to.fr, v);
lr[v].fr = min(lr[v].fr, lr[to.fr].fr);
lr[v].sc = max(lr[v].sc, lr[to.fr].sc);
if (lg[0][v].fr < lg[0][to.fr].fr + to.sc.fr){
swap(lg[0][v], lg[1][v]);
lg[0][v] = {lg[0][to.fr].fr + to.sc.fr, lg[0][to.fr].sc};
}
else if (lg[1][v].fr < lg[0][to.fr].fr + to.sc.fr)
lg[1][v] = {lg[0][to.fr].fr + to.sc.fr, lg[0][to.fr].sc};
}
}
tout[v] = tim;
if (g[v].size() == 1){
rv[v] = ++cnt;
lr[v] = {rv[v], rv[v]};
a.pb(v);
}
}
inline bool check (int v, int u){
return tin[v] <= tin[u] && tout[u] <= tout[v];
}
int lca (int v, int u){
if (check(v, u))
return v;
if (check(u, v))
return u;
for (int j = 19; j >= 0; j--)
if (p[v][j] && !check(p[v][j], u))
v = p[v][j];
return p[v][0];
}
inline int dis (int vv, int uu){
int pp = lca(vv, uu);
return h[1][vv] - h[1][pp] + h[0][uu] - h[0][pp];
}
void build (int v, int l, int r){
if (l == r){
t[v] = {dis(lc, a[l]), l};
return;
}
else {
int mid = (l + r) >> 1ll;
build(v + v, l, mid);
build(v + v + 1, mid + 1, r);
if (t[v + v].fr > t[v + v + 1].fr)
t[v] = t[v + v];
else
t[v] = t[v + v + 1];
}
}
//void upd(int l, int r, int val){
// for (l += n, r += n; l < r; l >>= 1, r >>= 1){
// if (l & 1)
// t[l++].fr += value;
// if (r & 1)
// t[--r].fr += value;
// }
//}
int hg;
void apply(int p, int value) {
t[p].fr += value;
if (p < cnt) lz[p] += value;
}
void push(int p) {
for (int s = hg; s > 0; --s) {
int i = p >> s;
if (lz[i] != 0) {
apply(i<<1, lz[i]);
apply(i<<1|1, lz[i]);
lz[i] = 0;
}
}
}
void build2(int p) {
while (p > 1) p >>= 1, t[p] = (t[p<<1].fr > t[p<<1|1].fr ? t[p<<1] : t[p<<1|1]), t[p].fr += lz[p];
}
void upd(int l, int r, int value) {
l += cnt, r += cnt;
int l0 = l, r0 = r;
for (; l < r; l >>= 1, r >>= 1) {
if (l&1) apply(l++, value);
if (r&1) apply(--r, value);
}
build2(l0);
build2(r0 - 1);
}
pi query(int l, int r) {
l += cnt, r += cnt;
push(l);
push(r - 1);
pi res = {0, 0};
for (; l < r; l >>= 1, r >>= 1){
if (l&1 && res.fr < t[l++].fr){
res = t[l - 1];
}
if (r&1 && res.fr < t[--r].fr){
res = t[r];
}
}
return res;
}
//void upd (int v, int l, int r, int ql, int qr, int val){
// push(v, l, r);
// if (ql <= l && r <= qr){
// lz[v] = val;
// push(v, l, r);
// return;
// }
// if (r < ql || qr < l)
// return;
// int mid = (l + r) >> 1ll;
// upd(v + v, l, mid, ql, qr, val);
// upd(v + v + 1, mid + 1, r, ql, qr, val);
// if (t[v + v].fr > t[v + v + 1].fr)
// t[v] = t[v + v];
// else
// t[v] = t[v + v + 1];
//}
void prec (int v, int pr = 0){
for (auto to : g[v]){
if (to.fr != pr){
prec(to.fr, v);
if (check(to.fr, lc))
w[to.fr] = to.sc.sc;
else
w[to.fr] = to.sc.fr;
}
}
}
int negr, negr2;
vector < pi > prs;
void reroot (int v, int pr = 0, pi up = {0, 0}){
if (up.fr > lg[0][v].fr){
prs.pb({v, up.sc});
lg[0][v] = up;
}
else
prs.pb({v, lg[0][v].sc});
for (auto to : g[v]){
if (to.fr != pr){
if (lg[0][v].sc == lg[0][to.fr].sc){
reroot(to.fr, v, {lg[1][v].fr + to.sc.sc, lg[1][v].sc});
}
else {
reroot(to.fr, v, {lg[0][v].fr + to.sc.sc, lg[0][v].sc});
}
}
}
}
main (){
ios_base::sync_with_stdio(0);
cin.tie(0);
a.pb(0);
cin >> n;
for (int i = 1; i < n; i++){
int a, b, c, d;
cin >> a >> b >> c >> d;
negr = c;
negr2 = d;
g[a].pb({b, {c, d}});
g[b].pb({a, {d, c}});
s += c + d;
}
if (n == 2){
ans[1] = max(negr, negr2);
ans[2] = s;
int q;
cin >> q;
for (int i = 1; i <= q; i++){
int e;
cin >> e;
cout << s - ans[e] << endl;
}
return 0;
}
for (int i = 1; i <= n; i++){
if (g[i].size() > 1){
rt = i;
break;
}
}
dfs(rt);
for (int i = 1; i <= n; i++){
ans[1] = max(ans[1], s_up - h[1][i] + h[0][i]);
}
reroot(rt);
int mx = 0;
for (pi it : prs){
int v = it.fr, u = it.sc;
int l = lca(v, u);
if (mx < s_up - h[1][l] + h[0][l] + h[0][v] + h[0][u] - 2 * h[0][l]){
mx = s_up - h[1][l] + h[0][l] + h[0][v] + h[0][u] - 2 * h[0][l];
x = v, y = u;
}
}
ans[2] = mx;
lc = lca(x, y);
cnt++;
hg = sizeof(int) * 8 - __builtin_clz(cnt);
prec(rt);
for (int i = 1; i < cnt; i++){
t[cnt + i].sc = i;
upd(i, i + 1, dis(lc, a[i]));
}
//build(1, 1, cnt);
del[0] = 1;
del[lc] = 1;
while (x != lc){
del[x] = 1;
upd(lr[x].fr, lr[x].sc + 1, -w[x]);
w[x] = 0;
x = p[x][0];
}
while (y != lc){
del[y] = 1;
upd(lr[y].fr, lr[y].sc + 1, -w[y]);
w[y] = 0;
y = p[y][0];
}
for (int i = 3; i < cnt; i++){
pi temp = query(1, cnt);
int it = temp.sc, val = temp.fr;
ans[i] = ans[i - 1] + val;
if (lr[lc].fr <= it && it <= lr[lc].sc){
int v = a[it];
while (!del[v]){
del[v] = 1;
upd(lr[v].fr, lr[v].sc + 1, -w[v]);
w[v] = 0;
v = p[v][0];
}
}
else {
int nw = lca(lc, a[it]);
int v = lc;
while (v != nw){
if (lr[v].fr > 1)
upd(1, lr[v].fr, -w[v]);
if (lr[v].sc < cnt)
upd(lr[v].sc + 1, cnt, -w[v]);
w[v] = 0;
v = p[v][0];
del[v] = 1;
}
v = a[it];
while (!del[v]){
del[v] = 1;
upd(lr[v].fr, lr[v].sc + 1, -w[v]);
w[v] = 0;
v = p[v][0];
}
}
}
for (int i = cnt + 1; i <= n; i++)
ans[i] = s;
int q;
cin >> q;
for (int i = 1; i <= q; i++){
int e;
cin >> e;
cout << s - ans[e] << endl;
}
}
Compilation message
designated_cities.cpp:212:5: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
212 | main (){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Execution timed out |
2086 ms |
43076 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Execution timed out |
2071 ms |
43316 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Execution timed out |
2086 ms |
43076 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
