#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 200010;
int mxp[maxn*4], fa[maxn], oval[maxn], dfn[maxn], rdfn[maxn], l[maxn], sz[maxn], vis[maxn], tval[maxn], tag[maxn], mx[maxn], val[maxn], del[maxn], e, n, q;
ll ans[maxn], dis[maxn];
int tot = 0;
int lst[maxn], cnt;
struct Edge {
int v, w, x;
} E[maxn*2];
ll t_val[maxn*4];
int t_mxp[maxn*4];
ll add[maxn*4];
inline ll Max(const ll &a, const ll &b) {
return a > b ? a : b;
}
inline int t_Max(const int &a, const int &b) {
return t_val[a] < t_val[b] ? b : a;
}
inline void addEdge(int u, int v, int w) {
E[e].v = v; E[e].x = l[u]; E[e].w = w; l[u] = e++;
}
void dfs_init(int u, int f) {
sz[u] = 1; mx[u] = 0;
lst[++cnt] = u;
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (v != f && !vis[v]) {
dfs_init(v, u);
sz[u] += sz[v];
mx[u] = Max(mx[u], sz[v]);
}
}
}
inline void pushUp(int rt) {
t_mxp[rt] = t_Max(t_mxp[rt<<1], t_mxp[rt<<1|1]);
}
void build(int l, int r, int rt) {
add[rt] = 0;
if (l == r) {
t_val[rt] = dis[rdfn[l]];
t_mxp[rt] = l;
return;
}
int m = (l + r) >> 1;
build(l, m, rt<<1);
build(m+1, r, rt<<1|1);
pushUp(rt);
}
inline void modify(const int &rt, const ll &v) {
t_val[rt] += v;
add[rt] += v;
}
inline void pushDown(int rt) {
if (add[rt]) {
modify(rt<<1, add[rt]);
modify(rt<<1|1, add[rt]);
add[rt] = 0;
}
}
void update(const int &L, const int &R, const int &v, int l, int r, int rt) {
if (L <= l && r <= R) {
modify(rt, v);
return;
}
pushDown(rt);
int m = (l + r) >> 1;
if (L <= m) update(L, R, v, l, m, rt<<1);
if (R > m) update(L, R, v, m+1, r, rt<<1|1);
pushUp(rt);
}
void dfs_cal(int u, int f, int t) {
fa[u] = f;
dfn[u] = ++tot; rdfn[tot] = u;
sz[u] = 1; tag[u] = t;
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (v != f && !vis[v]) {
val[v] = E[p].w;
oval[v] = E[p^1].w;
dis[v] = dis[u] + val[v];
dfs_cal(v, u, t);
sz[u] += sz[v];
}
}
}
ll cur_ans = 0;
inline void choose(int u) {
while (u && !del[u]) {
del[u] = 1;
update(dfn[u], dfn[u] + sz[u] - 1, -val[u], 1, tot, 1);
cur_ans += val[u];
u = fa[u];
}
}
void calans(int c) {
int t = tag[rdfn[t_mxp[1]]];
ll mxv = -1; int mxp = 0;
for (int i = 1; i <= cnt; i++) {
int u = lst[i];
if (u != c && tag[u] != tag[t]) {
if (dis[u] > mxv) {
mxv = dis[u];
mxp = u;
}
}
}
int u = mxp;
choose(u);
for (int i = 2; i <= cnt; i++) {
choose(rdfn[t_mxp[1]]);
ans[i] = max(ans[i], cur_ans);
}
}
namespace DP {
ll sum[maxn*2];
void dfs1(int u, int f, int fa_e) {
if (fa_e != -1) sum[fa_e] = E[fa_e].w;
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (v == f) continue;
dfs1(v, u, p^1);
if (fa_e != -1) {
sum[fa_e] += sum[p^1];
}
}
}
void dfs2(int u, int f) {
ll s = 0;
for (int p = l[u]; p >= 0; p = E[p].x) {
s += sum[p^1];
}
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (v == f) continue;
sum[p] = s - sum[p^1] + E[p].w;
}
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (v != f) {
dfs2(v, u);
}
}
}
void solve() {
dfs1(1, 0, -1);
dfs2(1, 0);
}
}
void solve(int u) {
cnt = 0;
dfs_init(u, 0);
int c = 0;
for (int i = 1; i <= cnt; i++) {
int t = lst[i];
tval[t] = Max(cnt-sz[t], mx[t]);
if (!c || tval[t] < tval[c]) c = t;
}
//处理过 c 的连通块
dis[c] = 0;
fa[c] = 0;
tot = 1;
dfn[c] = 1; rdfn[1] = c;
val[c] = oval[c] = 0;
int scnt = 0;
for (int p = l[c]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (!vis[v]) {
++ scnt;
val[v] = E[p].w;
oval[v] = E[p^1].w;
dis[v] = val[v];
fa[v] = c;
dfs_cal(v, c, v);
}
}
build(1, tot, 1);
ll sum = 0;
for (int i = 1; i <= cnt; i++) {
int t = lst[i];
sum += oval[t];
del[t] = 0;
for (int p = l[t]; p >= 0; p = E[p].x) {
if (vis[E[p].v]) sum += DP::sum[p^1];
}
}
ans[1] = Max(ans[1], sum);
if (scnt == 1) {
if (cnt == 2) {
for (int p = l[c]; p >= 0; p = E[p].x) {
if (!vis[E[p].v]) {
sum += val[E[p].v];
}
}
ans[2] = Max(ans[2], sum);
}
} else {
cur_ans = sum;
calans(c);
}
vis[c] = 1;
for (int p = l[c]; p >= 0; p = E[p].x) {
if (!vis[E[p].v]) {
solve(E[p].v);
}
}
}
int main() {
ll total_sum = 0;
memset(l, -1, sizeof(l));
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int A, B, C, D;
scanf("%d%d%d%d", &A, &B, &C, &D);
addEdge(A, B, C);
addEdge(B, A, D);
total_sum += C;
total_sum += D;
}
DP::solve();
solve(1);
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int k = 0;
scanf("%d", &k);
printf("%lld\n", total_sum-ans[k]);
}
return 0;
}
Compilation message
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:240:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
designated_cities.cpp:243:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &A, &B, &C, &D);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:251:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
designated_cities.cpp:254:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1280 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
1509 ms |
31836 KB |
Output is correct |
| 3 |
Execution timed out |
2016 ms |
48264 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1280 KB |
Output is correct |
| 2 |
Incorrect |
1817 ms |
31964 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1280 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
1509 ms |
31836 KB |
Output is correct |
| 3 |
Execution timed out |
2016 ms |
48264 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1280 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
