#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
//#define ll long long
#define int long long
template<class T>void chmax(T &a, T b){if (a < b)a = b;}
template<class T>void chmin(T &a, T b){if (b < a)a = b;}
using namespace std;
const int MAXN = (int)2e5 + 5;
const int L = 20;
vector <pii> g[MAXN];
vector <pii> G[MAXN];
int n, q;
int A[MAXN], B[MAXN], C[MAXN], D[MAXN];
int e[MAXN];
int answer[MAXN];
int dist[MAXN];
void calc(int v, int par, int len = 0) {
dist[v] = len;
for (auto [to, cost] : G[v]) {
if (to != par) {
calc(to, v, len + cost);
}
}
}
int tin[MAXN], tout[MAXN];
int tiktak = 0;
int pr[MAXN][L + 1];
void precalc(int v, int par) {
tin[v] = ++tiktak;
pr[v][0] = par;
for (int lv = 1; lv <= L; lv++) {
pr[v][lv] = pr[pr[v][lv - 1]][lv - 1];
}
for (auto [to, cost] : g[v]) {
if (to != par) {
precalc(to, v);
}
}
tout[v] = tiktak;
}
bool father(int a, int b) {
return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int get_lca(int a, int b) {
if (father(a, b)) {
return a;
}
if (father(b, a)) {
return b;
}
for (int lv = L; lv >= 0; lv--) {
if (!father(pr[a][lv], b)) {
a = pr[a][lv];
}
}
return pr[a][0];
}
void solve(int n, int a, int b) {
}
map <pii, int> edge;
int used[MAXN][2], used_id = 0;
void add(int x, int color) {
for (int i = 1; i < n; i++) {
int a = A[i];
int b = B[i];
if (father(a, b)) {
if (father(b, x)) {
used[i][0] = color;
} else {
used[i][1] = color;
}
}
else {
if (father(a, x)) {
used[i][1] = color;
}
else {
used[i][0] = color;
}
}
}
}
int center[MAXN];
void calc_center(int v, int par, int cur_sum) {
center[v] = cur_sum;
for (auto [to, cost] : g[v]) {
if (to != par) {
multiset <int> st;
int ed = edge[{v, to}];
st.insert(C[ed]);
st.insert(D[ed]);
int cur_cost;
auto it = st.begin();
if (*it == cost) {
it++;
}
cur_cost = *it;
calc_center(to, v, cur_sum - cur_cost + cost);
}
}
}
signed main() {
cin >> n;
for (int i = 1; i < n; i++) {
cin >> A[i] >> B[i] >> C[i] >> D[i];
int a = A[i];
int b = B[i];
int c = C[i];
int d = D[i];
edge[{b, a}] = edge[{a, b}] = i;
g[a].pb({b, c});
g[b].pb({a, d});
G[a].pb({b, c + d});
G[b].pb({a, c + d});
}
cin >> q;
for (int i = 1; i <= q; i++) {
cin >> e[i];
}
// calc tin tout
precalc(1, 1);
// case e[i] = 1
{
used_id = 1;
add(1, used_id);
int sum_root = 0;
int edge_sum = 0;
for (int i = 1; i < n; i++) {
if (used[i][0] == used_id) {
sum_root += C[i];
}
if (used[i][1] == used_id) {
sum_root += D[i];
}
edge_sum += C[i] + D[i];
}
calc_center(1, -1, sum_root);
int big = 1;
for (int i = 1; i <= n; i++) {
if (center[i] > center[big]) {
big = i;
}
}
answer[1] = edge_sum - center[big];
cout << answer[1] << endl;
exit(0);
}
}
/*
4
1 4 4 3
4 2 2 7
2 3 1 4
1
1
*/
Compilation message
designated_cities.cpp: In function 'void calc(long long int, long long int, long long int)':
designated_cities.cpp:34:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
34 | for (auto [to, cost] : G[v]) {
| ^
designated_cities.cpp: In function 'void precalc(long long int, long long int)':
designated_cities.cpp:51:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
51 | for (auto [to, cost] : g[v]) {
| ^
designated_cities.cpp: In function 'void calc_center(long long int, long long int, long long int)':
designated_cities.cpp:112:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
112 | for (auto [to, cost] : g[v]) {
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
9676 KB |
Output is correct |
2 |
Correct |
1270 ms |
102348 KB |
Output is correct |
3 |
Correct |
1608 ms |
148188 KB |
Output is correct |
4 |
Correct |
1256 ms |
102472 KB |
Output is correct |
5 |
Correct |
1401 ms |
102300 KB |
Output is correct |
6 |
Correct |
1398 ms |
109036 KB |
Output is correct |
7 |
Correct |
1274 ms |
101316 KB |
Output is correct |
8 |
Correct |
1595 ms |
149536 KB |
Output is correct |
9 |
Correct |
1128 ms |
100780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
9676 KB |
Output is correct |
2 |
Correct |
1270 ms |
102348 KB |
Output is correct |
3 |
Correct |
1608 ms |
148188 KB |
Output is correct |
4 |
Correct |
1256 ms |
102472 KB |
Output is correct |
5 |
Correct |
1401 ms |
102300 KB |
Output is correct |
6 |
Correct |
1398 ms |
109036 KB |
Output is correct |
7 |
Correct |
1274 ms |
101316 KB |
Output is correct |
8 |
Correct |
1595 ms |
149536 KB |
Output is correct |
9 |
Correct |
1128 ms |
100780 KB |
Output is correct |
10 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |