#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct xy { long long x, y, z; };
vector<xy>edge[212121];
long long D[212121], F[212121], FW[212121];
void get_DF(long long w,long long bef) {
D[w] = F[w] = 0; FW[w] = w;
for (xy E : edge[w]) if (E.x != bef) {
get_DF(E.x, w);
D[w] += D[E.x] + E.y;
if (F[w] < F[E.x] + E.z) {
F[w] = F[E.x] + E.z;
FW[w] = FW[E.x];
}
}
}
long long resX[212121], resY[212121], l[212121], r[212121];
void get_res(long long w, long long bef, long long fromRoot) {
long long sum = 0, cnt = 0;
vector<pair<long long, long long>>L;
for (xy E : edge[w]) if (E.x != bef) {
sum += D[E.x] + E.y;
L.push_back({ -(F[E.x] + E.z), FW[E.x] });
}
sort(L.begin(), L.end());
resX[w] = sum + fromRoot;
if (L.size() > 0)resY[w] = -(L[0].first) + sum + fromRoot, l[w] = w, r[w] = L[0].second;
if (L.size() > 1)resY[w] = -(L[0].first + L[1].first) + sum + fromRoot, l[w] = L[0].second, r[w] = L[1].second;
for (xy E : edge[w]) if (E.x != bef) get_res(E.x, w, fromRoot + sum - (D[E.x] + E.y) + E.z);
}
//segtree
struct ND { int l, r; long long max, maxw, pls; }tree[616161]; int treen = 1;
void update(int w) {
int l = tree[w].l, r = tree[w].r;
if (tree[l].max >= tree[r].max) tree[w].max = tree[l].max, tree[w].maxw = tree[l].maxw;
else tree[w].max = tree[r].max, tree[w].maxw = tree[r].maxw;
}
void spread(int w) {
long long l = tree[w].l, r = tree[w].r, pls = tree[w].pls;
tree[l].max += pls; tree[l].pls += pls;
tree[r].max += pls; tree[r].pls += pls;
tree[w].pls = 0;
}
void plsV(int now, int s, int e, int l, int r, long long v) {
if (s != e)spread(now);
if (s == l&&e == r) {
tree[now].pls += v;
tree[now].max += v;
if (l == r)tree[now].maxw = l;
return;
}
if (tree[now].l == 0) { tree[now].l = ++treen; tree[treen] = { 0, 0, 0, 0 }; }
if (tree[now].r == 0) { tree[now].r = ++treen; tree[treen] = { 0, 0, 0, 0 }; }
int m = (s + e) / 2;
if (l <= m)plsV(tree[now].l, s, m, l, min(r, m), v);
if (m + 1 <= r)plsV(tree[now].r, m + 1, e, max(l, m + 1), r, v);
update(now);
}
int getMinV() {
if (tree[1].max == 0)return -1;
return tree[1].maxw;
}
int S[212121], E[212121], R[212121], dfscnt = 0, pr[212121]; long long prV[212121], depth[212121], n;
void dfs(long long w, long long bef, long long befV, long long dep) {
S[w] = ++dfscnt; pr[w] = bef; prV[w] = befV; depth[w] = dep;
R[S[w]] = w;
for (xy E : edge[w]) if (E.x != bef) {
dfs(E.x, w, E.z, dep + E.z);
}
E[w] = dfscnt;
}
long long eraseE(long long w) {
if (prV[w] == 0)return 0;
plsV(1, 1, n, S[w], E[w], -prV[w]);
long long res = prV[w];
prV[w] = 0;
res+=eraseE(pr[w]);
return res;
}
long long ans[212121];
int main() {
long long i, j, allsum = 0; scanf("%lld", &n);
for (i = 0; i < n - 1; i++) {
long long s, e, a, b; scanf("%lld%lld%lld%lld", &s, &e, &a, &b);
allsum += a; allsum += b;
edge[s].push_back({ e, b, a });
edge[e].push_back({ s, a, b });
}
get_DF(1, -1);
get_res(1, -1, 0);
long long rootSum = 0, root = 1;
for (i = 1; i <= n; i++) if (ans[1] < resX[i])ans[1] = resX[i];
for (i = 1; i <= n; i++) if (rootSum < resY[i])rootSum = resY[i], root = i;
ans[1] = allsum - ans[1];
ans[2] = allsum - rootSum;
dfs(root, -1, 0, 0);
for (i = 1; i <= n; i++) {
plsV(1, 1, n, S[i], S[i], depth[i]);
}
eraseE(l[root]);
eraseE(r[root]);
for (i = 3; i <= n; i++) {
int v = R[getMinV()];
if (v == -1) { ans[i] = ans[i - 1]; continue; }
ans[i] = ans[i-1] - eraseE(v);
}
long long q, x; scanf("%lld", &q);
for (i = 0; i < q; i++) {
scanf("%lld", &x);
printf("%lld\n", ans[x]);
}
return 0;
}
Compilation message
designated_cities.c:2:9: fatal error: vector: No such file or directory
#include<vector>
^~~~~~~~
compilation terminated.
