#include <bits/stdc++.h>
using namespace std;
#define all(s) s.begin(), s.end()
#define int 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];
}
}
inline void push (int vv, int ll, int rr){
if (ll != rr){
lz[vv + vv] += lz[vv];
lz[vv + vv + 1] += lz[vv];
}
t[vv].fr += lz[vv];
lz[vv] = 0;
}
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});
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);
prec(rt);
build(1, 1, cnt);
del[0] = 1;
del[lc] = 1;
while (x != lc){
del[x] = 1;
upd(1, 1, cnt, lr[x].fr, lr[x].sc, -w[x]);
w[x] = 0;
x = p[x][0];
}
while (y != lc){
del[y] = 1;
upd(1, 1, cnt, lr[y].fr, lr[y].sc, -w[y]);
w[y] = 0;
y = p[y][0];
}
for (int i = 3; i <= cnt; i++){
int it = t[1].sc, val = t[1].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(1, 1, cnt, lr[v].fr, lr[v].sc, -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, 1, cnt, 1, lr[v].fr - 1, -w[v]);
if (lr[v].sc < cnt)
upd(1, 1, cnt, 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(1, 1, cnt, lr[v].fr, lr[v].sc, -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:157:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
157 | main (){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4936 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 |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
693 ms |
81352 KB |
Output is correct |
| 3 |
Correct |
703 ms |
90848 KB |
Output is correct |
| 4 |
Correct |
716 ms |
81352 KB |
Output is correct |
| 5 |
Correct |
744 ms |
82068 KB |
Output is correct |
| 6 |
Correct |
806 ms |
83976 KB |
Output is correct |
| 7 |
Correct |
690 ms |
82400 KB |
Output is correct |
| 8 |
Correct |
745 ms |
93896 KB |
Output is correct |
| 9 |
Correct |
646 ms |
90364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
710 ms |
81480 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4936 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 |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
693 ms |
81352 KB |
Output is correct |
| 3 |
Correct |
703 ms |
90848 KB |
Output is correct |
| 4 |
Correct |
716 ms |
81352 KB |
Output is correct |
| 5 |
Correct |
744 ms |
82068 KB |
Output is correct |
| 6 |
Correct |
806 ms |
83976 KB |
Output is correct |
| 7 |
Correct |
690 ms |
82400 KB |
Output is correct |
| 8 |
Correct |
745 ms |
93896 KB |
Output is correct |
| 9 |
Correct |
646 ms |
90364 KB |
Output is correct |
| 10 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 11 |
Incorrect |
710 ms |
81480 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4936 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
