#include <bits/stdc++.h>
#define pb emplace_back
#define all(x) x.begin(),x.end()
#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define fi first
#define se second
using namespace std;
typedef pair<ll,ll> pii;
const int maxN = 1e6+1;
const int inf = 1e9;
const int MOD = 1e9+7;
struct node{
int v;
ll w,c;
node(){};
node(int v,ll w,ll c){
this->v=v;
this->w=w;
this->c=c;
}
};
int n;
vector<node> a[maxN];
int l=20;
int up[maxN][21];
int in[maxN],out[maxN],timer=0;
ll pf[maxN];
pii tr[maxN];
int mxh=0;
ll ans=0;
vector<int> d[maxN];
bool anc(int p,int s){
return in[p]<=in[s]&&out[p]>=out[s];
}
int lca(int u,int v){
if(anc(u,v)) return u;
if(anc(v,u)) return v;
for(int i=l;i>=0;i--){
if(!anc(up[u][i],v)) u=up[u][i];
}return up[u][0];
}
void dfs(int x,int pre,int h){
in[x]=timer++;
up[x][0]=pre;
mxh=max(mxh,h);
d[h].pb(x);
for(int i=1;i<=l;i++){
up[x][i]=up[up[x][i-1]][i-1];
}
for(auto i:a[x]){
if(i.v==pre) continue;
tr[i.v]=pii(i.w,i.c);
dfs(i.v,x,h+1);
}
out[x]=timer++;
}
void buildPF(){
for(int i=1;i<n;i++){
int x=lca(i,i+1);
if(x==i){
pf[i+1]++;
pf[x]--;
}else if(x==i+1){
pf[i]++;
pf[x]--;
}else{
pf[i]++;
pf[i+1]++;
pf[x]-=2;
}
}
for(int i=mxh;i>0;i--){
for(int x:d[i]){
ans+=min(tr[x].fi*pf[x],tr[x].se);
pf[up[x][0]]+=pf[x];
}
}
}
int main()
{
fastio;
int u,v,w,c;
cin>>n;
for(int i=0;i<n-1;i++){
cin>>u>>v>>w>>c;
a[u].pb(node(v,w,c));
a[v].pb(node(u,w,c));
}dfs(1,1,0);
buildPF();
cout<<ans<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
47300 KB |
Output is correct |
2 |
Correct |
23 ms |
47616 KB |
Output is correct |
3 |
Correct |
23 ms |
47612 KB |
Output is correct |
4 |
Correct |
24 ms |
47684 KB |
Output is correct |
5 |
Correct |
24 ms |
47684 KB |
Output is correct |
6 |
Correct |
21 ms |
47336 KB |
Output is correct |
7 |
Correct |
21 ms |
47412 KB |
Output is correct |
8 |
Correct |
23 ms |
47528 KB |
Output is correct |
9 |
Correct |
25 ms |
47684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
118 ms |
69788 KB |
Output is correct |
2 |
Correct |
129 ms |
71232 KB |
Output is correct |
3 |
Correct |
131 ms |
74160 KB |
Output is correct |
4 |
Correct |
142 ms |
73660 KB |
Output is correct |
5 |
Correct |
23 ms |
47404 KB |
Output is correct |
6 |
Correct |
118 ms |
69164 KB |
Output is correct |
7 |
Correct |
85 ms |
63468 KB |
Output is correct |
8 |
Correct |
126 ms |
69736 KB |
Output is correct |
9 |
Correct |
95 ms |
70628 KB |
Output is correct |
10 |
Correct |
92 ms |
70028 KB |
Output is correct |
11 |
Correct |
99 ms |
71836 KB |
Output is correct |
12 |
Correct |
101 ms |
72132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
47300 KB |
Output is correct |
2 |
Correct |
23 ms |
47616 KB |
Output is correct |
3 |
Correct |
23 ms |
47612 KB |
Output is correct |
4 |
Correct |
24 ms |
47684 KB |
Output is correct |
5 |
Correct |
24 ms |
47684 KB |
Output is correct |
6 |
Correct |
21 ms |
47336 KB |
Output is correct |
7 |
Correct |
21 ms |
47412 KB |
Output is correct |
8 |
Correct |
23 ms |
47528 KB |
Output is correct |
9 |
Correct |
25 ms |
47684 KB |
Output is correct |
10 |
Correct |
118 ms |
69788 KB |
Output is correct |
11 |
Correct |
129 ms |
71232 KB |
Output is correct |
12 |
Correct |
131 ms |
74160 KB |
Output is correct |
13 |
Correct |
142 ms |
73660 KB |
Output is correct |
14 |
Correct |
23 ms |
47404 KB |
Output is correct |
15 |
Correct |
118 ms |
69164 KB |
Output is correct |
16 |
Correct |
85 ms |
63468 KB |
Output is correct |
17 |
Correct |
126 ms |
69736 KB |
Output is correct |
18 |
Correct |
95 ms |
70628 KB |
Output is correct |
19 |
Correct |
92 ms |
70028 KB |
Output is correct |
20 |
Correct |
99 ms |
71836 KB |
Output is correct |
21 |
Correct |
101 ms |
72132 KB |
Output is correct |
22 |
Correct |
125 ms |
67080 KB |
Output is correct |
23 |
Correct |
112 ms |
64764 KB |
Output is correct |
24 |
Correct |
127 ms |
66748 KB |
Output is correct |
25 |
Correct |
24 ms |
47452 KB |
Output is correct |
26 |
Correct |
59 ms |
56124 KB |
Output is correct |
27 |
Correct |
105 ms |
64112 KB |
Output is correct |
28 |
Correct |
86 ms |
67816 KB |
Output is correct |
29 |
Correct |
108 ms |
72048 KB |
Output is correct |
30 |
Correct |
101 ms |
71660 KB |
Output is correct |
31 |
Correct |
24 ms |
47588 KB |
Output is correct |