/*input
15
14 5 12 7
14 12 6 5
14 10 14 16
9 14 16 12
13 7 4 15
1 3 8 1
6 7 15 13
15 4 4 6
9 1 12 6
13 1 7 6
13 4 5 15
2 6 11 19
8 4 12 7
13 11 14 5
3
3
6
7
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
const int MAXN = 200007;
const int64_t INF = 1e17;
int N, Q, A[MAXN], B[MAXN], C[MAXN], D[MAXN];
int root = 0;
int64_t ans[MAXN], up[MAXN], down[MAXN], dep[MAXN];
int furthest[MAXN];
vector<int> adj[MAXN];
vector<int64_t> vals;
void dfs_down(int u, int p)
{
down[u] = 0;
furthest[u] = u;
for (int id : adj[u]) {
int v = A[id] ^ B[id] ^ u, c = (A[id] == u ? C[id] : D[id]);
if (v == p) continue;
dep[v] = dep[u] + c;
dfs_down(v, u);
if (dep[furthest[u]] < dep[furthest[v]]) furthest[u] = furthest[v];
down[u] += c + down[v];
}
}
void dfs_up(int u, int p)
{
int leaf[2] = {0, 0};
for (int id : adj[u]) {
int v = A[id] ^ B[id] ^ u, c = (A[id] == u ? C[id] : D[id]);
if (v == p) continue;
up[v] = up[u] + down[u] - down[v] + (C[id] ^ D[id] ^ c) - c;
dfs_up(v, u);
int cur = furthest[v];
if (dep[cur] > dep[leaf[0]]) swap(cur, leaf[0]);
if (dep[cur] > dep[leaf[1]]) swap(cur, leaf[1]);
}
if (up[u] + down[u] < ans[1]) ans[1] = up[u] + down[u];
if (up[u] + down[u] - dep[leaf[0]] - dep[leaf[1]] + 2 * dep[u] < ans[2]) {
ans[2] = up[u] + down[u] - dep[leaf[0]] - dep[leaf[1]] + 2 * dep[u];
root = leaf[0];
}
}
void dfs_calc(int u, int p, int64_t inc)
{
vals.push_back((u == furthest[u]) * inc);
for (int id : adj[u]) {
int v = A[id] ^ B[id] ^ u, c = (A[id] == u ? C[id] : D[id]);
if (v == p) continue;
dfs_calc(v, u, c + (furthest[u] == furthest[v]) * inc);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
for (int i = 0; i < N - 1; ++i) {
cin >> A[i] >> B[i] >> C[i] >> D[i];
adj[A[i]].push_back(i);
adj[B[i]].push_back(i);
}
ans[1] = ans[2] = INF;
vals.reserve(N);
dfs_down(1, 0);
dfs_up(1, 0);
dep[root] = 0, dfs_down(root, 0);
dfs_calc(root, 0, 0);
sort(vals.begin(), vals.end()), reverse(vals.begin(), vals.end());
int64_t total = accumulate(vals.begin(), vals.end(), 0ll);
assert(ans[2] == total - vals[0]);
for (int i = 2; i <= N; ++i) {
ans[i] = (total -= vals[i - 2]);
}
cin >> Q;
while (Q--) {
int x;
cin >> x;
cout << ans[x] << '\n';
}
}
Compilation message
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:104:18: error: 'accumulate' was not declared in this scope
int64_t total = accumulate(vals.begin(), vals.end(), 0ll);
^~~~~~~~~~
