#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 != v) {
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, b, c, d;
cin >> a >> b >> c >> d;
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);
}
//calc(1, -1);
//int a = 1;
//for (int i = 1; i <= n; i++) {
//if (dist[i] > dist[a]) {
//a = i;
//}
//}
//calc(a, -1);
//int b = 1;
//for (int i = 1; i <= n; i++) {
//if (dist[i] > dist[b]) {
//b = i;
//}
//}
//// a и b наш диаметр
//solve(n, a, b);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1686 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1698 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1686 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1686 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
