#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 = 1e5 + 7;
const int INF = 1e9 + 7;
pi t[4 * N];
int lz[4 * N];
int p[N][20], h[N], d[N], nega[N];
int tin[N], tout[N], tim;
int ans[N], sub[2][N];
int n, rt, s;
vector < pair < int, pi > > g[N];
pi lr[N];
int x, y, z;
int rv[N], del[N], cnt;
vector < int > a;
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){
nega[to.fr] = nega[v] + to.sc.fr;
h[to.fr] = h[v] + to.sc.fr - to.sc.sc;
dfs(to.fr, v);
sub[0][v] += sub[0][to.fr] + to.sc.sc;
sub[1][v] += sub[1][to.fr] + to.sc.fr;
lr[v] = {min(lr[to.fr].fr, lr[v].fr), max(lr[to.fr].sc, lr[v].sc)};
}
}
tout[v] = tim;
if (g[v].size() == 1){
rv[v] = ++cnt;
lr[v] = {rv[v], rv[v]};
a.pb(v);
}
}
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];
}
//4
//1 2 1 2
//1 3 3 4
//1 4 5 6
//3
//1
//2
//3
void prec (int v, int pr = 0){
for (auto to : g[v]){
if (to.fr != pr){
h[to.fr] = h[v] + to.sc.fr + to.sc.sc;
if (check(to.fr, a[x]) || check(to.fr, a[y])){
if (check(z, to.fr)){
d[to.fr] = d[v] + to.sc.fr + to.sc.sc;
del[to.fr] = 1;
}
else {
d[to.fr] = d[v] + to.sc.fr;
}
}
else {
d[to.fr] = d[v] + to.sc.sc;
}
prec(to.fr, v);
}
}
}
int dis (int v, int u){
int l = lca(v, u);
return (h[v] + h[u] - 2ll * h[l]) - (d[v] + d[u] - 2ll * d[l]);
}
void build (int v, int l, int r){
if (l == r){
t[v] = {dis(a[l], z), l};
}
else {
int mid = (l + r) >> 1;
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 push (int v, int l, int r){
if (l != r){
lz[v + v] += lz[v];
lz[v + v + 1] += lz[v];
}
t[v].fr += lz[v];
lz[v] = 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) >> 1;
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];
}
//pi get (int v, int l, int r, int ql, int qr){
// push(v, l, r);
// if (ql <= l && r <= qr)
// return t[v];
// if (r < ql || qr < l)
// return {-1, 0};
// int mid = (l + r) >> 1;
// return max(get(v + v, l, mid, ql, qr), get(v + v + 1, mid + 1, r, ql, qr));
//}
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;
dfs(rt);
// cout << rt << endl;
for (int i = 1; i <= n; i++){
ans[1] = max(ans[1], sub[0][rt] + h[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 < sub[0][rt] + h[l] + nega[v] + nega[u] - 2 * nega[l]){
mx = sub[0][rt] + h[l] + nega[v] + nega[u] - 2 * nega[l];
x = v, y = u;
}
}
}
ans[2] = mx;
// cout << x << ' ' << y << endl;
z = lca(x, y);
x = rv[x]; y = rv[y];
if (x > y)
swap(x, y);
prec(rt);
build(1, 1, cnt);
for (int i = 3; i <= cnt; i++){
int it = t[1].sc, val = t[1].fr;
// cout << a[it] << ' ' << val << endl;
ans[i] = ans[i - 1] + val;
if (lr[z].fr <= it && it <= lr[z].sc){
int v = a[it];
while (!del[v]){
del[v] = 1;
upd(1, 1, cnt, lr[v].fr, lr[v].sc, -((h[v] - h[p[v][0]]) - (d[v] - d[p[v][0]])));
v = p[v][0];
}
}
else {
int nz = lca(z, it);
if (lr[z].fr > 1)
upd(1, 1, cnt, 1, lr[z].fr - 1, -((h[z] - h[nz]) - (d[z] - d[nz])));
if (lr[z].sc < cnt)
upd(1, 1, cnt, lr[z].sc + 1, cnt, -((h[z] - h[nz]) - (d[z] - d[nz])));
int v = a[it];
while (!del[v]){
del[v] = 1;
upd(1, 1, cnt, lr[v].fr, lr[v].sc, -((h[v] - h[p[v][0]]) - (d[v] - d[p[v][0]])));
v = p[v][0];
}
}
}
// cout << cnt << endl;
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 |
Runtime error |
253 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
249 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
259 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
253 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
249 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
253 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
