#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
using namespace std;
struct nd{
vector<ll> ady;
}T[200010];
ll n,u,v,a,b,d[200010],f[200010][20],sum[200010],ans;
map< pll , pll > c;
void dfs(ll node,ll ant,ll dist){
d[ node ] = dist;
f[ node ][ 0 ] = ant;
for(auto sig:T[node].ady){
if( sig==ant ) continue;
dfs( sig , node , dist+1 );
}
return;
}
ll lca( ll A , ll B ){
if( d[ A ] < d[ B ] ) swap( A , B );
for(int i=19; i>=0; i--) if( d[A]-(1LL<<i) >= d[ B ] ){
A = f[ A ][ i ];
}
if( A==B ) return B;
for(int i=19; i>=0; i--){
if( f[A][i]!=f[B][i] ){
A = f[A][i];
B = f[B][i];
}
}
return f[A][0];
}
void compute(ll node, ll ant){
for(auto sig:T[node].ady){
if( sig == ant ) continue;
compute( sig , node );
sum[node]+=sum[sig];
}
if( node!=1 ) ans+=min( sum[node]*c[ { node , ant } ].fi , c[ { node , ant } ].se );
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i=1; i<n; i++){
cin >> u >> v >> a >> b;
c[ {u,v} ] = c[ {v,u} ] = {a,b};
T[u].ady.pb( v );
T[v].ady.pb( u );
}
dfs( 1 , 1 , 0 );
for(int pot=1; pot<20; pot++) for(int i=1; i<=n; i++) f[i][pot] = f[ f[i][pot-1] ][ pot-1 ];
for(int i=1; i<n; i++){
sum[i]++;
sum[i+1]++;
sum[ lca( i , i+1 ) ]-=2;
}
compute( 1 , 1 );
cout << ans;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
4984 KB |
Output is correct |
2 |
Correct |
10 ms |
5624 KB |
Output is correct |
3 |
Correct |
11 ms |
5752 KB |
Output is correct |
4 |
Correct |
11 ms |
5752 KB |
Output is correct |
5 |
Correct |
11 ms |
5752 KB |
Output is correct |
6 |
Correct |
8 ms |
5116 KB |
Output is correct |
7 |
Correct |
8 ms |
5240 KB |
Output is correct |
8 |
Correct |
12 ms |
5496 KB |
Output is correct |
9 |
Correct |
11 ms |
5752 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
405 ms |
42740 KB |
Output is correct |
2 |
Correct |
391 ms |
44792 KB |
Output is correct |
3 |
Correct |
434 ms |
48504 KB |
Output is correct |
4 |
Correct |
477 ms |
48784 KB |
Output is correct |
5 |
Correct |
9 ms |
5368 KB |
Output is correct |
6 |
Correct |
363 ms |
41848 KB |
Output is correct |
7 |
Correct |
234 ms |
31736 KB |
Output is correct |
8 |
Correct |
406 ms |
42744 KB |
Output is correct |
9 |
Correct |
194 ms |
44664 KB |
Output is correct |
10 |
Correct |
199 ms |
43384 KB |
Output is correct |
11 |
Correct |
206 ms |
46664 KB |
Output is correct |
12 |
Correct |
211 ms |
46588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
4984 KB |
Output is correct |
2 |
Correct |
10 ms |
5624 KB |
Output is correct |
3 |
Correct |
11 ms |
5752 KB |
Output is correct |
4 |
Correct |
11 ms |
5752 KB |
Output is correct |
5 |
Correct |
11 ms |
5752 KB |
Output is correct |
6 |
Correct |
8 ms |
5116 KB |
Output is correct |
7 |
Correct |
8 ms |
5240 KB |
Output is correct |
8 |
Correct |
12 ms |
5496 KB |
Output is correct |
9 |
Correct |
11 ms |
5752 KB |
Output is correct |
10 |
Correct |
405 ms |
42740 KB |
Output is correct |
11 |
Correct |
391 ms |
44792 KB |
Output is correct |
12 |
Correct |
434 ms |
48504 KB |
Output is correct |
13 |
Correct |
477 ms |
48784 KB |
Output is correct |
14 |
Correct |
9 ms |
5368 KB |
Output is correct |
15 |
Correct |
363 ms |
41848 KB |
Output is correct |
16 |
Correct |
234 ms |
31736 KB |
Output is correct |
17 |
Correct |
406 ms |
42744 KB |
Output is correct |
18 |
Correct |
194 ms |
44664 KB |
Output is correct |
19 |
Correct |
199 ms |
43384 KB |
Output is correct |
20 |
Correct |
206 ms |
46664 KB |
Output is correct |
21 |
Correct |
211 ms |
46588 KB |
Output is correct |
22 |
Correct |
455 ms |
40316 KB |
Output is correct |
23 |
Correct |
386 ms |
36284 KB |
Output is correct |
24 |
Correct |
446 ms |
40000 KB |
Output is correct |
25 |
Correct |
9 ms |
5372 KB |
Output is correct |
26 |
Correct |
171 ms |
21368 KB |
Output is correct |
27 |
Correct |
362 ms |
34808 KB |
Output is correct |
28 |
Correct |
165 ms |
40184 KB |
Output is correct |
29 |
Correct |
212 ms |
46584 KB |
Output is correct |
30 |
Correct |
203 ms |
46384 KB |
Output is correct |
31 |
Correct |
10 ms |
5628 KB |
Output is correct |