//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
llo n,m;
vector<llo> adj[2001];
vector<pair<pair<llo,llo>,llo>> pre[2001];
vector<pair<llo,llo>> pre2[2001];
vector<pair<llo,llo>> pre3[2001];
vector<llo> pre4[2001];
llo dp[2001][5001];
llo par[2001][20];
llo lev[2001];
llo st[2001];
llo ww[5001];
llo endd[2001];
llo val[2001][2001];
llo val2[2001];
llo co=0;
llo dp2[2001];
llo ind2[2001];
void dfs(llo no,llo par2=-1,llo levv=0){
//cout<<no<<",,"<<par2<<endl;
par[no][0]=par2;//par2;
lev[no]=levv;
st[no]=co;
co++;
for(auto j:adj[no]){
if(j!=par2){
dfs(j,no,levv+1);
}
}
endd[no]=co-1;
}
/*llo tree[2001];
void u(llo i,llo j){
while(i<=2000){
tree[i]+=j;
i+=(i&-i);
}
}
llo ss(llo i){
llo su=0;
while(i>0){
su+=tree[i];
i-=(i&-i);
}
return su;
}*/
void dfs2(llo no,llo par=-1){
llo su=0;
vector<llo> ac;
for(auto j:adj[no]){
if(j!=par){
dfs2(j,no);
su+=dp[j][0];
ind2[j]=ac.size();
ac.pb(j);
}
}
dp[no][0]=su;
for(auto j:ac){
val2[j]=0;
for(auto i:ac){
val[j][i]=0;
}
}
for(auto j:pre3[no]){
val2[j.a]=max(val2[j.a],dp[j.a][j.b]+ww[j.b]);
}
for(auto j:pre[no]){
val[j.a.a][j.a.b]=max(val[j.a.a][j.a.b],dp[j.a.a][j.b]+dp[j.a.b][j.b]+ww[j.b]);
val[j.a.b][j.a.a]=val[j.a.a][j.a.b];
}
if(ac.size()){
llo nn=ac.size();
for(llo j=0;j<(1<<nn);j++){
dp2[j]=0;
for(llo i=0;i<nn;i++){
if((1<<i)&j){
dp2[j]=max(dp2[j],val2[ac[i]]+dp2[j-(1<<i)]);
}
}
for(llo i=0;i<nn;i++){
for(llo k=i+1;k<nn;k++){
if((j&(1<<i)) and (j&(1<<k))){
dp2[j]=max(dp2[j],dp2[j-(1<<i)-(1<<k)]+val[ac[i]][ac[k]]);
}
}
}
}
dp[no][0]=max(dp[no][0],dp2[(1<<nn)-1]);
for(auto j:pre2[no]){
dp[no][j.b]=max(dp[no][j.b],dp2[(1<<nn)-1-(1<<ind2[j.a])]+dp[j.a][j.b]);
}
}
for(auto j:pre4[no]){
dp[no][j]=max(dp[no][j],dp[no][0]);
}
/* for(auto j:adj[no]){
if(j!=par){
u(st[no]+2,dp[j]);
u(endd[no]+2,-dp[j]);
u(st[j]+1,-dp[j]);
u(endd[no]+2,dp[j]);
}
}*/
/*llo xy=0;
for(auto j:pre[no]){
llo aa=j.a.a;
llo bb=j.a.b;
if(bb==no){
swap(aa,bb);
}
if(aa==no){
dp[no]=max(dp[no],ss(st[bb]+1)+j.b);
}
else{
llo cur=j.b;
cur+=ss(st[bb]+1);
cur+=ss(st[aa]+1);
cur-=dp[pre2[no][xy].a];
cur-=dp[pre2[no][xy].b];
dp[no]=max(dp[no],cur);
}
xy++;
}*/
/*for(int i=0;i<=m-(n-1);i++){
cout<<dp[no][i]<<",";
}
cout<<endl;
cout<<no<<","<<dp[no][0]<<endl;*/
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
vector<pair<pair<llo,llo>,llo>> ed;
for(llo i=0;i<m;i++){
llo aa,bb,cc;
cin>>aa>>bb>>cc;
aa--;
bb--;
if(cc==0){
adj[aa].pb(bb);
adj[bb].pb(aa);
}
else{
ed.pb({{aa,bb},cc});
}
}
/*llo cur=0;
for(llo i=0;i<n;i++){
if(adj[i].size()==1){
cur=i;
}
}*/
/* for(llo i=0;i<n;i++){
cout<<par[i][0]<<":";
}
cout<<endl;*/
dfs(0);
/*for(llo i=0;i<n;i++){
cout<<par[i][0]<<":";
}
cout<<endl;
*/
for(llo j=1;j<20;j++){
for(llo i=0;i<n;i++){
if(par[i][j-1]==-1){
par[i][j]=-1;
}
else{
par[i][j]=par[par[i][j-1]][j-1];
}
}
}
llo ans=0;
llo xy=0;;
for(auto j:ed){
xy++;
ww[xy]=j.b;
if((lev[j.a.a]+lev[j.a.b])%2==1){
ans+=j.b;
}
else{
llo aa=j.a.a;
llo bb=j.a.b;
if(lev[aa]>lev[bb]){
swap(aa,bb);
}
llo aa2=aa;
llo bb2=bb;
llo dif=lev[bb]-lev[aa];
for(llo j=0;j<20;j++){
if((1<<j)&dif){
bb=par[bb][j];
}
}
if(aa==bb){
llo cur=bb2;
while(par[cur][0]!=aa){
pre2[par[cur][0]].pb({cur,xy});
cur=par[cur][0];
}
pre3[aa].pb({cur,xy});
pre4[bb2].pb(xy);
// pre[aa2].pb({{aa2,bb2},j.b});
// pre2[aa2].pb({-1,-1});
// cout<<aa2<<","<<bb2<<","<<-1<<endl;
}
else{
for(llo j=19;j>=0;j--){
if(par[aa][j]!=par[bb][j]){
aa=par[aa][j];
bb=par[bb][j];
}
}
llo xx=par[aa][0];
llo cur=aa2;
while(cur!=aa){
pre2[par[cur][0]].pb({cur,xy});
cur=par[cur][0];
}
cur=bb2;
while(cur!=bb){
pre2[par[cur][0]].pb({cur,xy});
cur=par[cur][0];
}
pre[par[aa][0]].pb({{aa,bb},xy});
pre4[aa2].pb(xy);
pre4[bb2].pb(xy);
/*pre[par[aa][0]].pb({{aa2,bb2},j.b});
pre2[par[aa][0]].pb({aa,bb});*/
//cout<<aa2<<","<<bb2<<","<<aa<<","<<bb<<","<<par[aa][0]<<endl;
}
/* if(ind[j.a.a]<ind[j.a.b]){
pre[j.a.b].pb({j.a.a,j.b});
}
else{
pre[j.a.a].pb({j.a.b,j.b});
}*/
ans+=j.b;
}
}
dfs2(0);
/* for(llo i=0;i<n;i++){
for(auto j:pre[ss[i]]){
dp[i+1]=max(dp[i+1],dp[ind[j.a]]+j.b);
ans+=j.b;
}
dp[i+1]=max(dp[i+1],dp[i]);
}*/
ans-=dp[0][0];
cout<<ans<<endl;
return 0;
}
Compilation message
training.cpp: In function 'int main()':
training.cpp:234:9: warning: unused variable 'xx' [-Wunused-variable]
234 | llo xx=par[aa][0];
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
31724 KB |
Output is correct |
| 2 |
Correct |
40 ms |
34796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
13036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
37356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
10988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
45932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
