#include <bits/stdc++.h>
using namespace std;
#define sp << " " <<
#define int long long
#define vi vector<int>
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
const int N = 2e5+1;
int t = 1;
vi edges[N],v(N),w(N),pass(N,0),tin(N),tout(N),edg(N),pp(N),lazy(N,0);
set<int> sts[N];
map<pii,int> edgs;
int n;
void gg(int node,int p) {
edg[node] = edgs[{node,p}];
tin[node] = t++;
for (auto it : edges[node]) if (it != p) gg(it,node);
tout[node] = t++;
}
bool anc(int a,int b) {
return (tin[a] <= tin[b]) && (tout[a] >= tout[b]);
}
void dfs(int node,int p) {
for (auto it : edges[node]) if (it != p) dfs(it,node);
sts[node].insert(node);
for (auto it : edges[node]) {
if (it == p) continue;
if (sts[it].size() > sts[node].size()) sts[node].swap(sts[it]);
for (auto itt : sts[it]) {
int c = 2;
c-=(itt==1 || anc(it,itt-1));
c-=(itt==n || anc(it,itt+1));
pass[edg[it]]+=c;
}
for (auto itt : sts[it]) sts[node].insert(itt);
}
}
void dfsss(int node,int p) {
pp[node] = t++;
for (auto it : edges[node]) if (it != p) dfsss(it,node);
}
void yeter(int node,int p,int cur) {
cur+=lazy[node];
for (auto it : edges[node]) {
if (it != p) {
pass[edgs[{node,it}]]+=cur;
yeter(it,node,cur);
}
}
}
void solve() {
cin >> n;
vi ss(n+1,0);
F(i,n-1) {
int a,b;
cin >> a >> b >> v[i] >> w[i];
edges[a].push_back(b);
edges[b].push_back(a);
ss[a]++;
ss[b]++;
edgs[{a,b}] = edgs[{b,a}] = i;
}
if (*max_element(ss.begin(),ss.end()) <= 2){
int root;
for (int i=1;i<=n;i++) {
if (ss[i] == 1) root = i;
}
dfsss(root,root);
for (int i=2;i<=n;i++){
if (pp[i] < pp[i-1]) {
lazy[i]++;
lazy[i-1]--;
}
else {
lazy[i-1]++;
lazy[i]--;
}
}
yeter(root,root,0);
}
else {
gg(1,1);
dfs(1,1);
}
int ans = 0;
F(i,n-1) {
if (pass[i]*v[i] <= w[i]) ans+=pass[i]*v[i];
else ans+=w[i];
}
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
int t = 1;
//cin >> t;
F(i,t) solve();
}
Compilation message
putovanje.cpp: In function 'void solve()':
putovanje.cpp:80:10: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
80 | yeter(root,root,0);
| ~~~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
26968 KB |
Output is correct |
2 |
Incorrect |
10 ms |
27484 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
132 ms |
52308 KB |
Output is correct |
2 |
Correct |
137 ms |
52560 KB |
Output is correct |
3 |
Correct |
193 ms |
54612 KB |
Output is correct |
4 |
Correct |
158 ms |
55952 KB |
Output is correct |
5 |
Correct |
8 ms |
27228 KB |
Output is correct |
6 |
Correct |
143 ms |
51692 KB |
Output is correct |
7 |
Correct |
85 ms |
44424 KB |
Output is correct |
8 |
Correct |
163 ms |
52708 KB |
Output is correct |
9 |
Correct |
87 ms |
54612 KB |
Output is correct |
10 |
Correct |
84 ms |
53584 KB |
Output is correct |
11 |
Correct |
92 ms |
55916 KB |
Output is correct |
12 |
Correct |
98 ms |
55924 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
26968 KB |
Output is correct |
2 |
Incorrect |
10 ms |
27484 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |