也是 WA#2,1080pt,但是和提交记录中所有 80 分的错误信息都不一样……
不求帮助调代码,能否Hack或者分享一些易错点,谢谢!
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=5010;
const int inf=INT_MAX;
inline int read()
{
register int x=0;
register char c=getchar();
for(;!(c>='0'&&c<='9');c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+c-'0';
return x;
}
int n,X,Y;
vector<int>v[maxn],w[maxn];
int f[maxn],p[maxn];
int k[maxn];
int sum1,sum2;
void dfs(int fa,int x,int bian)
{
f[x]=fa,p[x]=p[fa]+bian;
for(register int i=0;i<v[x].size();i++)
if(v[x][i]!=fa&&(max(v[x][i],x)!=X||min(v[x][i],x)!=Y))
dfs(x,v[x][i],w[x][i]);
}
queue<pair<int,int> >q;
int bfs(int x,int zz,int XX)
{
register int ans=x;
pair<int,int>t;
if(zz==1) sum1=0;
else sum2=0;
k[x]=XX,q.push(make_pair(x,0));
while(!q.empty())
{
t=q.front(),q.pop();
if(zz==1&&sum1<t.second) sum1=t.second,ans=t.first;
if(zz==2&&sum2<t.second) sum2=t.second,ans=t.first;
for(register int i=0;i<v[t.first].size();i++)
if(k[v[t.first][i]]!=XX&&(max(t.first,v[t.first][i])!=X||min(t.first,v[t.first][i])!=Y))
k[v[t.first][i]]++,
q.push(make_pair(v[t.first][i],w[t.first][i]+t.second));
}
return ans;
}
int main()
{
n=read();
register int x,y,z,xx,yy;
for(register int i=1;i<n;i++)
{
x=read(),y=read(),z=read();
v[x].pb(y),v[y].pb(x);
w[x].pb(z),w[y].pb(z);
}
x=bfs(1,1,1),y=bfs(x,1,2);
register int Sum1,Sum2,ans=sum1;
for(register int i=1;i<=n;i++)
for(register int j=0;j<v[i].size();j++)
if(i>v[i][j])
{
memset(k,0,sizeof(k)),X=i,Y=v[i][j],z=w[i][j];
x=bfs(1,1,1),y=bfs(x,1,2),dfs(0,x,0);
Sum1=Sum2=0;
while(Sum1<sum1/2)
Sum1+=p[y]-p[f[y]],y=f[y];
Sum1=min(Sum1,sum1-Sum1);
for(register int ii=1;ii<=n;ii++)
if(!k[ii])
{
xx=bfs(ii,2,1),yy=bfs(xx,2,2),dfs(0,xx,0);
while(Sum2<sum2/2)
Sum2+=p[yy]-p[f[yy]],yy=f[yy];
Sum2=min(Sum2,sum2-Sum2);
break;
}
ans=min(ans,max(Sum1+Sum2+z,max(sum1,sum2)));
}
cout<<ans<<endl;
return 0;
}