#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];
int rev[500010];
int pow2[19];
inline int kpa(int x,int k)
{
for(;k>0;k^=k&-k)
x=spa[x][rev[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];
int cm[500010][19];
pi cut[500010][19];
inline pair<pi,pi>pth(int x,int k)
{
int ret=max({dp2[x].a,dp1[x].a+dp1[x].b});
pi ret2(dp1[x].a,-inf);
int len=0;
while(k>0)
{
int i=rev[k];
k-=pow2[i];
ret=max(ret,spd[x][i]);
ret2.se=max({cm[x][i]+len,ret2.se+pow2[i],ret2.fi+cut[x][i].se});
if(cut[x][i].fi+len>ret2.fi)
ret2.fi=cut[x][i].fi+len;
len+=pow2[i];
x=spa[x][i];
}
return pair<pi,pi>(pi(ret,x),ret2);
}
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].b));
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;i<18;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]+pow2[i],cm[spa[x][i]][i]+pow2[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+pow2[i]);
cut[x][i+1].se=max(cut[spa[x][i]][i].se,cut[x][i].se+pow2[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].b);
dp4[t].upd(max(dp4[x].get(td2),mx+mx2));
dfs2(t,x);
}
}
return;
}
const int bufsiz=1<<20;
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 spar[1000010][20];
vector<int>et;
int in[500010];
void dfs3(int x,int p)
{
in[x]=et.size();
et.eb(x);
for(int&t:adj[x])
if(t!=p)
dfs3(t,x),et.eb(x);
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
fread(buf,1,bufsiz,stdin);
int n,m;
n=getint(),m=getint();
for(int i=0;i<19;i++)
pow2[i]=1<<i;
for(int i=0;i++<n;)
rev[i]=__builtin_ctz(i);
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);
dfs3(1,0);
{
int en=et.size();
for(int i=0;i<en;i++)
spar[i][0]=in[et[i]];
for(int i=0;i<19;i++)
for(int j=0;j+pow2[i+1]<=n;j++)
spar[j][i+1]=min(spar[j][i],spar[j+pow2[i]][i]);
}
for(auto&t:ev)
{
int u=t.fi.fi;
int v=t.fi.se;
int w=t.se;
int l;
{
if(in[u]<in[v])
{
int lv=31-__builtin_clz(in[v]-in[u]+1);
l=et[min(spar[in[u]][lv],spar[in[v]-pow2[lv]+1][lv])];
}
else
{
int lv=31-__builtin_clz(in[u]-in[v]+1);
l=et[min(spar[in[v]][lv],spar[in[u]-pow2[lv]+1][lv])];
}
}
int len=dep[u]+dep[v]-dep[l]*2;
int dmax=0,cmax=0;
if(v==l)
swap(u,v);
if(u==l)
{
auto qq=pth(v,dep[v]-dep[l]-1);
int&q1=qq.fi.fi;
auto&q2=qq.se;
int&y=qq.fi.se;
q2.se++;
{
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
{
auto qqu=pth(u,dep[u]-dep[l]-1);
auto qqv=pth(v,dep[v]-dep[l]-1);
int&qu1=qqu.fi.fi;
int&qv1=qqv.fi.fi;
auto&qu2=qqu.se;
auto&qv2=qqv.se;
int&yu=qqu.fi.se;
int&yv=qqv.fi.se;
qu2.se++,qv2.se++;
{
int fcu1=dp1[yu].a+1;
int fcv1=dp1[yv].a+1;
int fcu2=max(dp2[yu].a,dp1[yu].a+dp1[yu].b);
int fcv2=max(dp2[yv].a,dp1[yv].a+dp1[yv].b);
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:226:10: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
226 | fread(buf,1,bufsiz,stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int getint()':
Main.cpp:194:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
194 | fread(buf,1,bufsiz,stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:204:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
204 | fread(buf,1,bufsiz,stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:258:35: warning: iteration 18 invokes undefined behavior [-Waggressive-loop-optimizations]
258 | for(int j=0;j+pow2[i+1]<=n;j++)
| ~~~~~~~~^
Main.cpp:257:22: note: within this loop
257 | for(int i=0;i<19;i++)
| ~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
37628 KB |
Output is correct |
| 2 |
Correct |
25 ms |
37632 KB |
Output is correct |
| 3 |
Incorrect |
26 ms |
37632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
37628 KB |
Output is correct |
| 2 |
Correct |
25 ms |
37632 KB |
Output is correct |
| 3 |
Incorrect |
26 ms |
37632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
41216 KB |
Output is correct |
| 2 |
Correct |
30 ms |
41208 KB |
Output is correct |
| 3 |
Correct |
31 ms |
41084 KB |
Output is correct |
| 4 |
Correct |
31 ms |
40960 KB |
Output is correct |
| 5 |
Correct |
30 ms |
40960 KB |
Output is correct |
| 6 |
Correct |
28 ms |
40824 KB |
Output is correct |
| 7 |
Correct |
31 ms |
41216 KB |
Output is correct |
| 8 |
Correct |
30 ms |
41080 KB |
Output is correct |
| 9 |
Correct |
29 ms |
41216 KB |
Output is correct |
| 10 |
Correct |
30 ms |
40960 KB |
Output is correct |
| 11 |
Correct |
30 ms |
41088 KB |
Output is correct |
| 12 |
Correct |
29 ms |
40832 KB |
Output is correct |
| 13 |
Correct |
30 ms |
40960 KB |
Output is correct |
| 14 |
Correct |
31 ms |
40960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
37628 KB |
Output is correct |
| 2 |
Correct |
25 ms |
37632 KB |
Output is correct |
| 3 |
Incorrect |
26 ms |
37632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
37628 KB |
Output is correct |
| 2 |
Correct |
25 ms |
37632 KB |
Output is correct |
| 3 |
Incorrect |
26 ms |
37632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
37628 KB |
Output is correct |
| 2 |
Correct |
25 ms |
37632 KB |
Output is correct |
| 3 |
Incorrect |
26 ms |
37632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
37628 KB |
Output is correct |
| 2 |
Correct |
25 ms |
37632 KB |
Output is correct |
| 3 |
Incorrect |
26 ms |
37632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
37628 KB |
Output is correct |
| 2 |
Correct |
25 ms |
37632 KB |
Output is correct |
| 3 |
Incorrect |
26 ms |
37632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
