#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define ft first
#define sd second
#define all(x) x.begin(),x.end()
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
const int N = 200100;
const int PW = 20;
vector<int> vc, g[N];
int U[N], V[N], C1[N], C2[N], kol[N], n, pr[N][PW], V1[N], V2[N];
int tin[N], tout[N], tt = 0, ad[N];
ll ans = 0, sm[N];
void dfs(int v, int p){
tin[v] = tt++;
pr[v][0] = p;
for (int po = 1; po < PW; po++)
pr[v][po] = pr[pr[v][po - 1]][po - 1];
for (int nm : g[v]){
int u = (U[nm] == v ? V[nm] : U[nm]);
if (u == p) continue;
V1[u] = C1[nm];
V2[u] = C2[nm];
dfs(u, v);
}
tout[v] = tt++;
}
bool upper(int a, int b){
return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int a, int b){
if (upper(a, b)) return a;
if (upper(b, a)) return b;
for (int po = PW - 1; po >= 0; po--)
if (!upper(pr[a][po], b))
a = pr[a][po];
return pr[a][0];
}
void DFS(int v){
sm[v] = 0;
for (int nm : g[v]){
int u = (U[nm] == v ? V[nm] : U[nm]);
if (u == pr[v][0]) continue;
DFS(u);
sm[v] += sm[u];
}
sm[v] += ad[v];
ans += min(ll(V1[v]) * ll(sm[v]), ll(V2[v]));
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("in.txt","r",stdin);
cin >> n;
for (int i = 1; i < n; i++){
cin >> U[i] >> V[i] >> C1[i] >> C2[i];
U[i]--; V[i]--;
g[U[i]].PB(i);
g[V[i]].PB(i);
}
dfs(0, 0);
for (int i = 1; i < n; i++){
int lc = lca(i, i - 1);
ad[i]++;
ad[i - 1]++;
ad[lc] -= 2;
}
DFS(0);
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
9 ms |
5376 KB |
Output is correct |
3 |
Correct |
9 ms |
5376 KB |
Output is correct |
4 |
Correct |
9 ms |
5504 KB |
Output is correct |
5 |
Correct |
9 ms |
5504 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Correct |
8 ms |
5248 KB |
Output is correct |
8 |
Correct |
8 ms |
5376 KB |
Output is correct |
9 |
Correct |
9 ms |
5376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
23672 KB |
Output is correct |
2 |
Correct |
115 ms |
24824 KB |
Output is correct |
3 |
Correct |
132 ms |
27384 KB |
Output is correct |
4 |
Correct |
145 ms |
27000 KB |
Output is correct |
5 |
Correct |
8 ms |
5248 KB |
Output is correct |
6 |
Correct |
110 ms |
23292 KB |
Output is correct |
7 |
Correct |
76 ms |
18424 KB |
Output is correct |
8 |
Correct |
122 ms |
23932 KB |
Output is correct |
9 |
Correct |
87 ms |
24696 KB |
Output is correct |
10 |
Correct |
89 ms |
24184 KB |
Output is correct |
11 |
Correct |
97 ms |
25848 KB |
Output is correct |
12 |
Correct |
96 ms |
25976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
9 ms |
5376 KB |
Output is correct |
3 |
Correct |
9 ms |
5376 KB |
Output is correct |
4 |
Correct |
9 ms |
5504 KB |
Output is correct |
5 |
Correct |
9 ms |
5504 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Correct |
8 ms |
5248 KB |
Output is correct |
8 |
Correct |
8 ms |
5376 KB |
Output is correct |
9 |
Correct |
9 ms |
5376 KB |
Output is correct |
10 |
Correct |
117 ms |
23672 KB |
Output is correct |
11 |
Correct |
115 ms |
24824 KB |
Output is correct |
12 |
Correct |
132 ms |
27384 KB |
Output is correct |
13 |
Correct |
145 ms |
27000 KB |
Output is correct |
14 |
Correct |
8 ms |
5248 KB |
Output is correct |
15 |
Correct |
110 ms |
23292 KB |
Output is correct |
16 |
Correct |
76 ms |
18424 KB |
Output is correct |
17 |
Correct |
122 ms |
23932 KB |
Output is correct |
18 |
Correct |
87 ms |
24696 KB |
Output is correct |
19 |
Correct |
89 ms |
24184 KB |
Output is correct |
20 |
Correct |
97 ms |
25848 KB |
Output is correct |
21 |
Correct |
96 ms |
25976 KB |
Output is correct |
22 |
Correct |
141 ms |
21984 KB |
Output is correct |
23 |
Correct |
111 ms |
19960 KB |
Output is correct |
24 |
Correct |
128 ms |
21624 KB |
Output is correct |
25 |
Correct |
8 ms |
5248 KB |
Output is correct |
26 |
Correct |
56 ms |
12664 KB |
Output is correct |
27 |
Correct |
111 ms |
19320 KB |
Output is correct |
28 |
Correct |
75 ms |
22392 KB |
Output is correct |
29 |
Correct |
96 ms |
25976 KB |
Output is correct |
30 |
Correct |
93 ms |
25592 KB |
Output is correct |
31 |
Correct |
8 ms |
5376 KB |
Output is correct |