// Se eu pegar um cara qualquer e definir que ele vai ser um resort e minha raiz
// eu posso fazer um guloso escolhendo sempre o cara mais fundo e atualizando a profundidade
// dos outros, o problema é que eu nao necessariamente preciso pegar essa raiz
// entao eu teria q brutar todas as possiveis, o que ficaria n^2, já pega n<=2000 though
// Faço um centroid e em cada nivel eu escolho sempre caras de pelo menos duas subarvores
// diferentes, se a melhor resposta n tiver ai so descer nos filhos e ta safe
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;
// template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '['; string sep = ""; for (const auto &x : v) os << sep << x, sep = ", "; return os << ']'; }
// template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
// #ifdef MY_DEBUG_FLAG
// void debug() { cerr << endl; }
// template<typename Ini, typename... Fim> void debug(Ini I, Fim... F) { cerr << I; if(sizeof...(F)) cerr << ", "; debug(F...);}
// #define db(...) cerr << "DEBUG (" << #__VA_ARGS__ << ") == ", debug(__VA_ARGS__)
// #else
// #define db(...) 1
// #endif
using ll = long long;
#define int ll
#define pb push_back
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
constexpr int maxn = 2e5+10;
vector<pair<int,int>> g[maxn];
ll ans[maxn];
struct Centroid {
bool mark[maxn]; int sz[maxn];
void pre(int u, int p = 0) {
sz[u] = 1;
for(auto [v, w] : g[u]) if(!mark[v] && v != p)
pre(v, u), sz[u] += sz[v];
}
int get(int u) {
for(auto [v, w] : g[u]) if((sz[v] << 1) > sz[u] && !mark[v])
return (sz[u] -= sz[v], sz[v] += sz[u], get(v));
return u;
}
ll dfs(int u, int p, ll& cost, vector<pair<ll,int>>& guloso, int idx) {
vector<ll> td;
ll maior = 0;
for(auto [v, w] : g[u]) {
if(v == p) cost += w;
else if(!mark[v]) {
ll gld = dfs(v, u, cost, guloso, idx) + w;
td.pb(gld);
if(gld > maior) maior = gld;
}
}
bool ok = 0;
for(ll a : td) {
if(a == maior && !ok) ok = 1;
else guloso.pb({a, idx});
}
return maior;
}
void decompose(int u, ll add) {
pre(u); u = get(u);
mark[u] = 1;
static vector<ll> custo; custo.clear();
static vector<pair<ll,int>> guloso; guloso.clear();
int idx = 0;
ll custo_tot = 0;
guloso.pb({0, -1});
for(auto [v, w] : g[u]) {
if(mark[v]) continue;
ll cost = 0;
ll gld = dfs(v, u, cost, guloso, idx) + w;
guloso.pb({gld, idx});
custo.pb(cost); custo_tot += cost;
++idx;
}
// db(u, add, guloso, custo, custo_tot);
sort(all(guloso));
reverse(all(guloso));
// ans[1] = max(ans[1], custo_tot + add);
idx = guloso.front().second;
int primeiro = 0;
for(int i = 0; i < sz(guloso); i++)
if(guloso[i].second != idx) { primeiro = i; break; }
ll bom = custo_tot, foi = guloso[primeiro].first;
for(int i = 0; i < sz(guloso); i++) {
bom += guloso[i].first;
if(primeiro == i) foi = 0;
ans[i + 1 + (foi>0)] = max(ans[i + 1 + (foi>0)], bom + foi + add);
}
ll val = 0;
vector<ll> suf;
for(int i = sz(custo)-1; i >= 0; i--)
suf.pb(val), val += custo[i];
reverse(all(suf));
val = 0;
int i = 0;
for(auto [v, w] : g[u]) {
if(mark[v]) continue;
decompose(v, val + suf[i] + w);
val += custo[i];
++i;
}
}
} centroid;
ll aq[maxn];
struct AAA
{
int v, w, back;
};
vector<AAA> g_esp[maxn];
void pre_caso1(int u, int p) {
// fprintf(stderr, "pre %lld\n", u);
for(auto [v, w, back] : g_esp[u]) {
if(v == p) continue;
pre_caso1(v, u);
aq[u] += aq[v] + back;
}
// fprintf(stderr, "pre %lld %lld\n", u, aq[u]);
}
void caso1(int u, int p) {
// fprintf(stderr, "noraml %lld %lld\n", u, aq[u]);
ans[1] = max(ans[1], aq[u]);
for(auto [v, w, back] : g_esp[u]) {
if(v == p) continue;
aq[v] += w + aq[u] - back;
// fprintf(stderr, "uv %lld %lld %lld %lld\n", u, v, aq[v], aq[v]);
caso1(v, u);
}
}
int32_t main() {
int n; scanf("%lld", &n);
ll tot = 0;
for(int i = 1; i < n; i++) {
int a, b, c, d; scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
g[a].pb({b, c});
g[b].pb({a, d});
tot += c + d;
g_esp[a].pb({b, c, d});
g_esp[b].pb({a, d, c});
}
// centroid.decompose(1, 0);
// for(int i = 1; i <= n; i++)
// ans[i] = max(ans[i], ans[i-1]);
pre_caso1(1, 0);
caso1(1, 0);
int q; scanf("%lld", &q);
while(q--) {
int e; scanf("%lld", &e); assert(e == 1);
printf("%lld\n", tot - ans[e]);
}
}
Compilation message
designated_cities.cpp: In function 'int32_t main()':
designated_cities.cpp:162:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
162 | int n; scanf("%lld", &n);
| ~~~~~^~~~~~~~~~~~
designated_cities.cpp:165:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | int a, b, c, d; scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:181:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
181 | int q; scanf("%lld", &q);
| ~~~~~^~~~~~~~~~~~
designated_cities.cpp:183:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
183 | int e; scanf("%lld", &e); assert(e == 1);
| ~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
15 ms |
19404 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 2 |
Incorrect |
345 ms |
41020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
14 ms |
19404 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
15 ms |
19404 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 2 |
Incorrect |
345 ms |
41020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
15 ms |
19404 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
