本人在测试时发现
int jump(int x,int k,int v)
{
int maxx=-1e18;
for(int i=18;i>=0;i--)
{
if(dep[f[x][i]]>=dep[k])
{
if(max1[x][i]==v)maxx=max(maxx,max2[x][i]);
else maxx=max(maxx,max1[x][i]);
//这里应该有一条语句x=f[x][i]
}
}
return maxx;
}
//以下是主程序的一部分
for(int i=1;i<=m;i++)
{
if(!vis[i])
{
int lc=lca(w[i].a,w[i].b);
int a=jump(w[i].a,lc,w[i].c);
int b=jump(w[i].b,lc,w[i].c);
res=min(res,(ans-max(a,b)+w[i].c));
}
}
在处理函数jump的时候,没有将x向上跳来更新答案,竟然过了
数据过水