#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)2e5 + 10;
const int LOG = 20;
vector<pii> T[N];
int idx[N];
ll cnt[N];
ll c1[N], c2[N];
int par[LOG][N];
int tin[N];
int tout[N];
int tt;
void dfs(int u, int pr){
tin[u] = ++tt;
par[0][u]=pr;
for(int i = 1; i < LOG; i ++ )
par[i][u]=par[i-1][par[i-1][u]];
for(auto x : T[u]){
if(x.fi == pr) continue;
idx[x.fi]=x.se;
dfs(x.fi, u);
}
tout[u] = tt;
}
bool is_anc(int a, int b){
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b){
if(is_anc(a,b))return a;
if(is_anc(b,a))return b;
for(int i = LOG - 1; i >= 0 ; i -- )
if(!is_anc(par[i][a],b))a=par[i][a];
return par[0][a];
}
ll ans = 0;
void dfs2(int u, int pr){
for(auto x : T[u]){
if(x.fi == pr) continue;
dfs2(x.fi, u);
cnt[u] += cnt[x.fi];
}
if(pr == -1) return;
ans += min(cnt[u] * 1ll * c1[idx[u]], c2[idx[u]]);
}
int main(){
fastIO;
int n;
cin >> n;
int u, v;
for(int i = 1; i < n; i ++ ){
cin >> u >> v >> c1[i] >> c2[i];
T[u].push_back(mp(v,i));
T[v].push_back(mp(u,i));
}
dfs(1,1);
for(int i = 1; i < n; i ++ ){
cnt[i]++;
cnt[i+1]++;
cnt[lca(i,i + 1)] -= 2 ;
}
dfs2(1,-1);
cout << ans << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
9 ms |
5376 KB |
Output is correct |
3 |
Correct |
9 ms |
5504 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 |
5248 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 |
5504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
138 ms |
21368 KB |
Output is correct |
2 |
Correct |
126 ms |
22392 KB |
Output is correct |
3 |
Correct |
137 ms |
24184 KB |
Output is correct |
4 |
Correct |
142 ms |
23928 KB |
Output is correct |
5 |
Correct |
7 ms |
5248 KB |
Output is correct |
6 |
Correct |
119 ms |
20984 KB |
Output is correct |
7 |
Correct |
74 ms |
16888 KB |
Output is correct |
8 |
Correct |
118 ms |
23160 KB |
Output is correct |
9 |
Correct |
84 ms |
24056 KB |
Output is correct |
10 |
Correct |
83 ms |
23544 KB |
Output is correct |
11 |
Correct |
90 ms |
25208 KB |
Output is correct |
12 |
Correct |
94 ms |
25336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
9 ms |
5376 KB |
Output is correct |
3 |
Correct |
9 ms |
5504 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 |
5248 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 |
5504 KB |
Output is correct |
10 |
Correct |
138 ms |
21368 KB |
Output is correct |
11 |
Correct |
126 ms |
22392 KB |
Output is correct |
12 |
Correct |
137 ms |
24184 KB |
Output is correct |
13 |
Correct |
142 ms |
23928 KB |
Output is correct |
14 |
Correct |
7 ms |
5248 KB |
Output is correct |
15 |
Correct |
119 ms |
20984 KB |
Output is correct |
16 |
Correct |
74 ms |
16888 KB |
Output is correct |
17 |
Correct |
118 ms |
23160 KB |
Output is correct |
18 |
Correct |
84 ms |
24056 KB |
Output is correct |
19 |
Correct |
83 ms |
23544 KB |
Output is correct |
20 |
Correct |
90 ms |
25208 KB |
Output is correct |
21 |
Correct |
94 ms |
25336 KB |
Output is correct |
22 |
Correct |
135 ms |
21880 KB |
Output is correct |
23 |
Correct |
119 ms |
19832 KB |
Output is correct |
24 |
Correct |
137 ms |
21496 KB |
Output is correct |
25 |
Correct |
8 ms |
5376 KB |
Output is correct |
26 |
Correct |
50 ms |
12536 KB |
Output is correct |
27 |
Correct |
111 ms |
19192 KB |
Output is correct |
28 |
Correct |
73 ms |
21752 KB |
Output is correct |
29 |
Correct |
90 ms |
25336 KB |
Output is correct |
30 |
Correct |
87 ms |
24956 KB |
Output is correct |
31 |
Correct |
8 ms |
5376 KB |
Output is correct |