#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];
int rv[N], del[N], cnt;
vector < int > a;
int lc, x, y;
void dfs (int v, int pr = 0){
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);
}
}
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) {
cout << "wtf" << endl;
exit(0);
}
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;
}
}
}
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;
g[a].pb({b, {c, d}});
g[b].pb({a, {d, c}});
s += c + d;
}
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]);
}
int mx = 0;
for (int i = 1; i <= cnt; i++){
for (int j = i + 1; j <= cnt; j++){
int v = a[i], u = a[j];
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:133:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
133 | main (){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
