#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);
}
};
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 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)});
while(k>0)
{
int i=__builtin_ctz(k);
k^=k&-k;
ret=max(ret,spd[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;
ret.se=-inf;
int len=0;
while(k>0)
{
int i=__builtin_ctz(k);
k^=k&-k;
ret.se=max({cm[x][i]+len,ret.se+(1<<i),ret.fi+cut[x][i].se});
ret.fi=max(ret.fi,cut[x][i].fi+len);
len+=1<<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]=dpex[x];
cm[x][0]=dpe[x];
cut[x][0].fi=dpe[x]+1;
cut[x][0].se=dpe[x];
for(int i=0,y=x;i<18;y=spa[y][i++])
{
if(spa[x][i]==0)
break;
spd[x][i+1]=max(spd[x][i],spd[spa[x][i]][i]);
cm[x][i+1]=max({cm[x][i]+(1<<i),cm[spa[x][i]][i]+(1<<i),
cut[x][i].fi+cut[spa[x][i]][i].se});
cut[x][i+1].fi=max(cut[x][i].fi,cut[spa[x][i]][i].fi+(1<<i));
cut[x][i+1].se=max(cut[spa[x][i]][i].se,cut[x][i].se+(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]-1);
auto q2=pth(v,dep[v]-dep[l]-1);
q2.fi++,q2.se++;
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(fc1==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]-1);
int qv1=dpth(v,dep[v]-dep[l]-1);
auto qu2=pth(u,dep[u]-dep[l]-1);
auto qv2=pth(v,dep[v]-dep[l]-1);
qu2.se++,qv2.se++;
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:223:10: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
223 | fread(buf,1,bufsiz,stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int getint()':
Main.cpp:203:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
203 | fread(buf,1,bufsiz,stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:213:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
213 | fread(buf,1,bufsiz,stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
37632 KB |
Output is correct |
| 2 |
Correct |
32 ms |
37624 KB |
Output is correct |
| 3 |
Correct |
28 ms |
37632 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
37624 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
37632 KB |
Output is correct |
| 2 |
Correct |
32 ms |
37624 KB |
Output is correct |
| 3 |
Correct |
28 ms |
37632 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
37624 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
40320 KB |
Output is correct |
| 2 |
Correct |
33 ms |
40448 KB |
Output is correct |
| 3 |
Correct |
35 ms |
40192 KB |
Output is correct |
| 4 |
Correct |
33 ms |
40144 KB |
Output is correct |
| 5 |
Correct |
31 ms |
40056 KB |
Output is correct |
| 6 |
Correct |
29 ms |
39936 KB |
Output is correct |
| 7 |
Correct |
36 ms |
40388 KB |
Output is correct |
| 8 |
Correct |
32 ms |
40192 KB |
Output is correct |
| 9 |
Correct |
37 ms |
40448 KB |
Output is correct |
| 10 |
Correct |
30 ms |
40056 KB |
Output is correct |
| 11 |
Correct |
32 ms |
40320 KB |
Output is correct |
| 12 |
Correct |
38 ms |
40064 KB |
Output is correct |
| 13 |
Correct |
39 ms |
40312 KB |
Output is correct |
| 14 |
Correct |
44 ms |
40184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
37632 KB |
Output is correct |
| 2 |
Correct |
32 ms |
37624 KB |
Output is correct |
| 3 |
Correct |
28 ms |
37632 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
37624 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
37632 KB |
Output is correct |
| 2 |
Correct |
32 ms |
37624 KB |
Output is correct |
| 3 |
Correct |
28 ms |
37632 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
37624 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
37632 KB |
Output is correct |
| 2 |
Correct |
32 ms |
37624 KB |
Output is correct |
| 3 |
Correct |
28 ms |
37632 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
37624 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
37632 KB |
Output is correct |
| 2 |
Correct |
32 ms |
37624 KB |
Output is correct |
| 3 |
Correct |
28 ms |
37632 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
37624 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
37632 KB |
Output is correct |
| 2 |
Correct |
32 ms |
37624 KB |
Output is correct |
| 3 |
Correct |
28 ms |
37632 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
37624 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
