이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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)] -- ;
}
dfs2(1,-1);
cout << ans << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |