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"
using namespace std;
#define ar array
const int N = 5e5 + 5;
vector<int> edges[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin>>n>>m;
vector<ar<int, 3>> e;
int cnt = 0;
for(int i=0;i<m;i++){
int a, b, c; cin>>a>>b>>c; a++, b++;
if(c == 1){
edges[a].push_back(b);
edges[b].push_back(a);
cnt++;
} else {
e.push_back({a, b, c});
}
}
assert(cnt == n - 1);
int res = 0;
vector<int> d(n + 1);
function<void(int, int)> dfs = [&](int u, int p){
for(auto x : edges[u]){
if(x == p) continue;
d[x] = d[u] + 1;
dfs(x, u);
}
};
int a = 1;
d[a] = 0, dfs(a, a);
for(int i=1;i<=n;i++){
if(d[i] > d[a]) a = i;
}
d[a] = 0, dfs(a, a);
for(int i=1;i<=n;i++){
if(d[i] > d[a]) a = i;
}
res = 2 * n - 2 - d[a];
for(auto x : e){
int a = x[0], b = x[1], c = x[2];
vector<int> par(n + 1), used(n + 1), d(n + 1);
function<void(int)> dfs = [&](int u){
for(auto x : edges[u]){
if(x == par[u]) continue;
par[x] = u, dfs(x);
}
}; dfs(a);
vector<int> tt;
while(b){ used[b] = 1;
tt.push_back(b);
b = par[b];
}
function<void(int)> dfs2 = [&](int u){
used[u] = 1; d[u] = 0;
for(auto x : edges[u]){
if(used[x]) continue;
dfs2(x);
d[u] = max(d[u], d[x] + 1);
}
};
int mx = 0, cyc = tt.size();
for(auto x : tt){
dfs2(x);
}
for(int i=1;i<cyc;i++){
mx = max(mx, d[tt[i]] + d[tt[i-1]]);
}
//~ cout<<a<<" "<<b<<" "<<c<<" "<<mx<<" "<<cyc<<"\n";
//~ cout<<c<<"\n";
//~ for(auto x : tt) cout<<x<<" ";
//~ cout<<"\n";
res = min(res, 2 * n - 2 - mx - cyc + c);
}
cout<<res<<"\n";
}
# | 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... |