#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
struct max3
{
int a,b,c;
max3(){a=b=c=0;}
inline void upd(int x)
{
if(x>a)
c=b,b=a,a=x;
else if(x>b)
c=b,b=x;
else if(x>c)
c=x;
return;
}
inline int get()
{
return a;
}
inline int get(int x)
{
return x==a?b:a;
}
inline int get(int x,int y)
{
if(x<y)
swap(x,y);
return x==a?(y==b?c:b):(y==a?b:a);
}
};
struct max4
{
int a,b,c,d;
max4(){a=b=c=d=0;}
inline void upd(int x)
{
if(x>a)
d=c,c=b,b=a,a=x;
else if(x>b)
d=c,c=b,b=x;
else if(x>c)
d=c,c=x;
else if(x>d)
d=x;
return;
}
inline int get()
{
return a;
}
inline int get(int x)
{
return x==a?b:a;
}
inline int get(int x,int y)
{
if(x<y)
swap(x,y);
return x==a?(y==b?c:b):(y==a?b:a);
}
inline int get(int x,int y,int z)
{
if(x<y)
swap(x,y);
if(x<z)
swap(x,z);
if(y<z)
swap(y,z);
return x==a?(y==b?(z==c?d:c):(z==b?c:b)):(y==a?(z==b?c:b):(z==a?b:a));
}
};
vector<int>adj[500010];
int depth[500010];
void ddfs(int x,int p)
{
depth[x]=depth[p]+1;
for(int&t:adj[x])
if(t!=p)
ddfs(t,x);
return;
}
int dep[500010];
int spa[500010][19];
inline int kpa(int x,int k)
{
for(;k>0;k^=k&-k)
x=spa[x][__builtin_ctz(k)];
return x;
}
inline int lca(int x,int y)
{
if(dep[x]>dep[y])
x=kpa(x,dep[x]-dep[y]);
else
y=kpa(y,dep[y]-dep[x]);
if(x==y)
return x;
for(int i=19;i-->0;)
if(spa[x][i]!=spa[y][i])
x=spa[x][i],y=spa[y][i];
return spa[x][0];
}
max3 dp1[500010],dp2[500010];
int dpex[500010],dpe[500010];
int child[500010][19];
int spd[500010][19];
inline int dpth(int x,int k)
{
int ret=max({dp2[x].a,dp1[x].a+dp1[x].get(dp1[x].a)});
int y=x;
{
int i=__builtin_ctz(k);
k^=k&-k;
ret=max(ret,spd[x][i]);
y=child[x][i];
x=spa[x][i];
}
while(k>0)
{
int i=__builtin_ctz(k);
k^=k&-k;
ret=max({ret,spd[x][i],dpex[y]});
y=child[x][i];
x=spa[x][i];
}
return ret;
}
int cm[500010][19];
pi cut[500010][19];
inline pi pth(int x,int k)
{
pi ret;
ret.fi=dp1[x].a;
int len=0;
int y=x;
{
int i=__builtin_ctz(k);
k^=k&-k;
len=1<<i;
ret.se=max(cm[x][i],ret.fi+cut[x][i].se);
ret.fi=max(ret.fi,cut[x][i].fi);
y=child[x][i];
x=spa[x][i];
}
while(k>0)
{
int i=__builtin_ctz(k);
k^=k&-k;
{
int cur=dpe[y];
ret.se=max({ret.se+(1<<i),cm[x][i]+len,
ret.fi+cut[x][i].se,ret.fi+cur+(1<<i),cut[x][i].se+cur+len});
ret.fi=max({ret.fi-len,cut[x][i].fi,cur})+len;
}
len+=1<<i;
y=child[x][i];
x=spa[x][i];
}
return ret;
}
max4 dp3[500010];
max3 dp4[500010];
void sdfs(int x,int p)
{
spa[x][0]=p;
for(int i=0;i<18;i++)
spa[x][i+1]=spa[spa[x][i]][i];
dep[x]=dep[p]+1;
for(int&t:adj[x])
if(t!=p)
sdfs(t,x),dp1[x].upd(dp1[t].a+1),
dp2[x].upd(max(dp2[t].a,dp1[t].a+dp1[t].get(dp1[t].a)));
dp3[x].a=dp1[x].a;
dp3[x].b=dp1[x].b;
dp3[x].c=dp1[x].c;
dp4[x]=dp2[x];
return;
}
void dfs2(int x,int p)
{
spd[x][0]=cm[x][0]=cut[x][0].fi=cut[x][0].se=0;
for(int i=0,y=x;i<18;y=spa[y][i++])
{
if(spa[x][i]==0)
break;
child[x][i]=y;
{
spd[x][i+1]=max({spd[x][i],spd[spa[x][i]][i],dpex[y]});
}
{
int cur=dpe[y];
cm[x][i+1]=max({cm[x][i],cm[spa[x][i]][i],
cut[x][i].fi+cut[spa[x][i]][i].se-(1<<i),cut[x][i].fi+cur,cut[spa[x][i]][i].se+cur})+(1<<i);
cut[x][i+1].fi=max({cut[x][i].fi-(1<<i),cut[spa[x][i]][i].fi,cur})+(1<<i);
cut[x][i+1].se=max({cut[spa[x][i]][i].se-(1<<i),cut[x][i].se,cur})+(1<<i);
}
}
for(int&t:adj[x])
{
if(t!=p)
{
int fc1=dp1[t].a+1;
int fc2=max(dp2[t].a,dp1[t].a+dp1[t].get(dp1[t].a));
dpex[t]=max(dp2[x].get(fc2),dp1[x].get(fc1)+dp1[x].get(dp1[x].get(fc1),fc1));
dpe[t]=dp1[x].get(dp1[t].a+1);
int mx=dp3[x].get(dp1[t].a+1);
dp3[t].upd(mx+1);
int mx2=dp3[x].get(mx,dp1[t].a+1);
int td2=max(dp2[t].a,dp1[t].a+dp1[t].get(dp1[t].a));
dp4[t].upd(max(dp4[x].get(td2),mx+mx2));
dfs2(t,x);
}
}
return;
}
const int bufsiz=1<<18;
char buf[bufsiz+10];
int bcnt;
inline int getint()
{
int a=0;
while(buf[bcnt]<'0'||buf[bcnt]>'9')
{
bcnt++;
if(bcnt==bufsiz)
{
fread(buf,1,bufsiz,stdin);
bcnt=0;
}
}
while(buf[bcnt]>='0'&&buf[bcnt]<='9')
{
a=a*10+buf[bcnt]-'0';
bcnt++;
if(bcnt==bufsiz)
{
fread(buf,1,bufsiz,stdin);
bcnt=0;
}
}
return a;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
fread(buf,1,bufsiz,stdin);
int n,m;
n=getint(),m=getint();
vector<pair<pi,int> >ev;
for(int i=0;i<m;i++)
{
int u,v,w;
u=getint(),v=getint(),w=getint();
u++,v++;
if(w==1)
adj[u].eb(v),adj[v].eb(u);
else if(w*2<n)
ev.eb(pi(u,v),w);
}
sdfs(1,0);
int ans=inf;
{
int d1=max_element(dep+1,dep+n+1)-dep;
ddfs(d1,0);
ans=2*n-1-*max_element(depth+1,depth+n+1);
}
dfs2(1,0);
for(auto&t:ev)
{
int u=t.fi.fi;
int v=t.fi.se;
int w=t.se;
int l=lca(u,v);
int len=dep[u]+dep[v]-dep[l]*2;
int dmax=0,cmax=0;
if(v==l)
swap(u,v);
if(u==l)
{
auto q1=dpth(v,dep[v]-dep[l]);
auto q2=pth(v,dep[v]-dep[l]);
int y=kpa(v,dep[v]-dep[l]-1);
{
int fc1=dp1[y].a+1;
int fc2=max(dp2[y].a,dp1[y].a+dp1[y].get(dp1[y].a));
int get1=0,get2=0;
{
if(fc1==dp3[l].a)
get1=dp3[l].b,get2=dp3[l].c;
else
{
get1=dp3[l].a;
if(mx==dp3[l].b)
get2=dp3[l].c;
else
get2=dp3[l].b;
}
}
dmax=max({q1,dp4[l].get(fc2),get1+get2});
}
{
int cur=dp3[l].get(dp1[y].a+1);
cmax=max(q2.se,q2.fi+cur);
}
}
else
{
int qu1=dpth(u,dep[u]-dep[l]);
int qv1=dpth(v,dep[v]-dep[l]);
auto qu2=pth(u,dep[u]-dep[l]);
auto qv2=pth(v,dep[v]-dep[l]);
int yu=kpa(u,dep[u]-dep[l]-1);
int yv=kpa(v,dep[v]-dep[l]-1);
{
int fcu1=dp1[yu].a+1;
int fcv1=dp1[yv].a+1;
int fcu2=max(dp2[yu].a,dp1[yu].a+dp1[yu].get(dp1[yu].a));
int fcv2=max(dp2[yv].a,dp1[yv].a+dp1[yv].get(dp1[yv].a));
int get1=0,get2=0;
{
int mx=max(fcu1,fcv1),mn=min(fcu1,fcv1);
if(mx==dp3[l].a)
{
if(mn==dp3[l].b)
get1=dp3[l].c,get2=dp3[l].d;
else if(mn==dp3[l].c)
get1=dp3[l].b,get2=dp3[l].d;
else
get1=dp3[l].b,get2=dp3[l].c;
}
else if(mn==dp3[l].a)
get1=dp3[l].b,get2=dp3[l].c;
else
{
get1=dp3[l].a;
if(mx==dp3[l].b)
{
if(mn==dp3[l].c)
get2=dp3[l].d;
else
get2=dp3[l].c;
}
else
get2=dp3[l].b;
}
}
dmax=max({qu1,qv1,dp4[l].get(fcu2,fcv2),get1+get2});
}
{
int cur=dp3[l].get(dp1[yu].a+1,dp1[yv].a+1);
cmax=max({qu2.se+(dep[v]-dep[l]),qv2.se+(dep[u]-dep[l]),qu2.fi+qv2.fi,
qu2.fi+cur+(dep[v]-dep[l]),qv2.fi+cur+(dep[u]-dep[l])});
}
}
ans=min(ans,n*2-2-dmax-len+w);
ans=min(ans,n*2-4-cmax+w);
}
cout<<ans<<endl;
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:307:28: error: 'mx' was not declared in this scope; did you mean 'm'?
307 | if(mx==dp3[l].b)
| ^~
| m
Main.cpp:260:10: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
260 | fread(buf,1,bufsiz,stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int getint()':
Main.cpp:240:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
240 | fread(buf,1,bufsiz,stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:250:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
250 | fread(buf,1,bufsiz,stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
