#include <bits/stdc++.h>
#define sz(c) int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
#define fore(c,...) for (auto __VA_ARGS__:(c))
using namespace std;
typedef long long ll;
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
cout<<fixed<<setprecision(10);
int N;
cin>>N;
vector<vector<pair<int,int>>> adj(N);
vector<pair<int,int>> cost(N-1);
rep(i,0,N-1) {
int a,b,c1,c2;
cin>>a>>b>>c1>>c2;
a--,b--;
adj[a].emplace_back(b,i);
adj[b].emplace_back(a,i);
cost[i]={c1,c2};
}
vector<ll> cnt(N-1);
vector<set<pair<int,bool>>> s(N);
function<void(int,int)> dfs=[&](int v,int p) {
if (v>0) s[v].emplace(v,false);
if (v<N-1) s[v].emplace(v,true);
int k=-1;
fore(adj[v],e) {
int u=e.first;
if (u==p) {
k=e.second;
continue;
}
dfs(u,v);
if (sz(s[v])<sz(s[u])) s[v].swap(s[u]);
fore(s[u],t) {
pair<int,bool> x={t.first,!t.second};
if (t.second) x.first++; else x.first--;
auto it=s[v].find(x);
if (it!=s[v].end()) s[v].erase(it); else s[v].insert(t);
}
set<pair<int,bool>>().swap(s[u]);
}
if (k!=-1) cnt[k]+=sz(s[v]);
};
dfs(0,-1);
ll res=0;
rep(i,0,N-1) res+=min(cost[i].first*cnt[i],(ll)cost[i].second);
cout<<res<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
7 ms |
632 KB |
Output is correct |
3 |
Correct |
10 ms |
632 KB |
Output is correct |
4 |
Correct |
10 ms |
632 KB |
Output is correct |
5 |
Correct |
10 ms |
632 KB |
Output is correct |
6 |
Correct |
6 ms |
376 KB |
Output is correct |
7 |
Correct |
6 ms |
504 KB |
Output is correct |
8 |
Correct |
8 ms |
504 KB |
Output is correct |
9 |
Correct |
8 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
190 ms |
28536 KB |
Output is correct |
2 |
Correct |
191 ms |
30696 KB |
Output is correct |
3 |
Correct |
223 ms |
35928 KB |
Output is correct |
4 |
Correct |
224 ms |
33760 KB |
Output is correct |
5 |
Correct |
7 ms |
504 KB |
Output is correct |
6 |
Correct |
191 ms |
25848 KB |
Output is correct |
7 |
Correct |
139 ms |
20728 KB |
Output is correct |
8 |
Correct |
209 ms |
25996 KB |
Output is correct |
9 |
Correct |
167 ms |
29436 KB |
Output is correct |
10 |
Correct |
172 ms |
28664 KB |
Output is correct |
11 |
Correct |
173 ms |
30844 KB |
Output is correct |
12 |
Correct |
180 ms |
30968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
7 ms |
632 KB |
Output is correct |
3 |
Correct |
10 ms |
632 KB |
Output is correct |
4 |
Correct |
10 ms |
632 KB |
Output is correct |
5 |
Correct |
10 ms |
632 KB |
Output is correct |
6 |
Correct |
6 ms |
376 KB |
Output is correct |
7 |
Correct |
6 ms |
504 KB |
Output is correct |
8 |
Correct |
8 ms |
504 KB |
Output is correct |
9 |
Correct |
8 ms |
632 KB |
Output is correct |
10 |
Correct |
190 ms |
28536 KB |
Output is correct |
11 |
Correct |
191 ms |
30696 KB |
Output is correct |
12 |
Correct |
223 ms |
35928 KB |
Output is correct |
13 |
Correct |
224 ms |
33760 KB |
Output is correct |
14 |
Correct |
7 ms |
504 KB |
Output is correct |
15 |
Correct |
191 ms |
25848 KB |
Output is correct |
16 |
Correct |
139 ms |
20728 KB |
Output is correct |
17 |
Correct |
209 ms |
25996 KB |
Output is correct |
18 |
Correct |
167 ms |
29436 KB |
Output is correct |
19 |
Correct |
172 ms |
28664 KB |
Output is correct |
20 |
Correct |
173 ms |
30844 KB |
Output is correct |
21 |
Correct |
180 ms |
30968 KB |
Output is correct |
22 |
Correct |
338 ms |
15736 KB |
Output is correct |
23 |
Correct |
330 ms |
14424 KB |
Output is correct |
24 |
Correct |
324 ms |
15608 KB |
Output is correct |
25 |
Correct |
7 ms |
504 KB |
Output is correct |
26 |
Correct |
142 ms |
7416 KB |
Output is correct |
27 |
Correct |
266 ms |
13228 KB |
Output is correct |
28 |
Correct |
141 ms |
26232 KB |
Output is correct |
29 |
Correct |
182 ms |
30840 KB |
Output is correct |
30 |
Correct |
179 ms |
30760 KB |
Output is correct |
31 |
Correct |
7 ms |
760 KB |
Output is correct |