#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
struct Edge{
ll cost[2];
int to;
Edge(){}
Edge(int a,int b,int c){
to = a,cost[0] = b,cost[1] = c;
}
};
const int mxn = 2e5+10;
vector<Edge> tree[mxn];
int bit[mxn];
pll val[mxn];
ll add[mxn],del[mxn];
int dep[mxn],idx[mxn],link_top[mxn],sz[mxn],par[mxn],bs[mxn],cnt;
int n;
void modify(int p,int v){
for(;p<mxn;p+=p&-p)bit[p] += v;
return;
}
ll getval(int p){
ll re= 0;
for(;p>0;p-= p&-p)re += bit[p];
return re;
}
void dfs1(int now){
sz[now] = 1;
for(auto nxt:tree[now]){
if(nxt.to == par[now])continue;
par[nxt.to] = now;
dep[nxt.to] = dep[now]+1;
val[nxt.to] = {nxt.cost[0],nxt.cost[1]};
dfs1(nxt.to);
if(!bs[now]||sz[bs[now]]<sz[nxt.to])bs[now] = nxt.to;
}
return;
}
void dfs2(int now,int top){
link_top[now] = top;
idx[now] = ++cnt;
if(bs[now])dfs2(bs[now],top);
for(auto nxt:tree[now]){
if(nxt.to == bs[now]||nxt.to == par[now])continue;
dfs2(nxt.to,nxt.to);
}
return;
}
void addval(int a,int b,int c){
int ta = link_top[a],tb = link_top[b];
while(ta != tb){
if(dep[ta]<dep[tb]){
swap(ta,tb);
swap(a,b);
}
modify(idx[ta],c);
modify(idx[a]+1,-c);
a = par[ta];ta = link_top[a];
}
if(dep[a]>dep[b])swap(a,b);
modify(idx[a],c);
modify(idx[b]+1,-c);
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i = 1;i<n;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
tree[a].push_back(Edge(b,c,d));
tree[b].push_back(Edge(a,c,d));
}
par[1] = 0;
dep[1] = 1;
dfs1(1);
dfs2(1,1);
for(int i = 2;i<=n;i++){
addval(i-1,i,1);
}
ll ans = 0;
for(int i = 2;i<=n;i++){
ans += min(getval(idx[i])*val[i].fs,val[i].sc);
}
cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12380 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
27224 KB |
Output is correct |
| 2 |
Correct |
52 ms |
28736 KB |
Output is correct |
| 3 |
Correct |
76 ms |
32852 KB |
Output is correct |
| 4 |
Correct |
58 ms |
31824 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12636 KB |
Output is correct |
| 6 |
Correct |
49 ms |
26896 KB |
Output is correct |
| 7 |
Incorrect |
34 ms |
24448 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12380 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
