This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define sz(x) (int)(x.size())
using namespace std;
using namespace __gnu_pbds;
typedef
tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int n, k, m;
vector<int> vaut;
vector<vector<pair<int, int>>> adj;
vector<int> memo;
int dp(int s) {
if (s>=n) return 0;
if (memo[s]!=-1) return memo[s];
int ans=dp(s+1);
for (auto u: adj[s]) {
ans=max(ans, dp(u.first)+u.second);
}
return memo[s]=ans;
}
void solve() {
cin >> n >> m;
vaut.clear();
vaut.resize(n);
adj.clear();
adj.resize(n);
memo.clear();
memo.resize(n, -1);
vector<int> temp[n];
for (int i=0; i<n-1; i++) {
int u, v, c; cin >> u >> v >> c;
u--, v--;
temp[u].push_back(v);
temp[v].push_back(u);
}
int act=0;
for (int i=0; i<n; i++) {
if (temp[i].size()==1) act=i;
}
int prec=0;
for (int i=0; i<n; i++) {
vaut[act]=i;
int pro=act;
for (auto u: temp[act]) {
if (u!=prec) act=u;
}
prec=pro;
}
int ans=0;
for (int i=n-1; i<m; i++) {
int u, v, c; cin >> u >> v >> c;
u--, v--;
u=vaut[u], v=vaut[v];
if (u>v) swap(u, v);
if ((v-u)%2==0) {
adj[u].push_back({v, c});
}
ans+=c;
}
cout << ans-dp(0) << endl;
return;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt=1;// cin >> tt;
while(tt--) solve();
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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |