P3304 40分 求助```cpp #include #include #include #include #include using namespace std; typedef long long int LL; struct node{ int v,w; }edge; int n,k,pre[200010],next[200010],ans1; LL dis[200010],ds[200010],dt[200010],cntt[20010],cnts[200010],ans; vector G[200010]; bool vis[200010]; int bfs(int s) { memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); memset(pre,0,sizeof(pre)); dis[s]=0;vis[s]=1; queue q;q.push(s); while(!q.empty()) { int u=q.front();q.pop(); for(int i=0;i<G[u].size();i++) { if(!vis[G[u][i].v]) { vis[G[u][i].v]=1;pre[G[u][i].v]=u; dis[G[u][i].v]=dis[u]+G[u][i].w; q.push(G[u][i].v); } } } ans=0; int t=0; for(int i=1;i<=n;i++) { if(dis[i]>ans) { ans=dis[i]; t=i; } } return t; } void dp(int u,int fa,LL d[],LL cnt[]) { for(int i=0;i<G[u].size();i++) { int v=G[u][i].v,w=G[u][i].w; if(v!=fa) { dp(v,u,d,cnt); if(d[u]<d[v]+w)d[u]=d[v]+w,cnt[u]=1; else if(d[u]==d[v]+w)cnt[u]++; } } } int main() { cin>>n; for(int i=1;i<=n;i++)cnts[i]=1; for(int i=1;i<=n;i++)cntt[i]=1; for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); edge.v=v;edge.w=w; G[u].push_back(edge); edge.v=u; G[v].push_back(edge); } int s=bfs(1); int t=bfs(s); dp(s,0,ds,cnts); dp(t,0,dt,cntt); int u=t,v=pre[u]; while(v) { next[v]=u; if(cntt[u]>1)break; u=v;v=pre[v]; } v=next[u]; while(u!=t) { if(cnts[u]>1)break; ans1++; u=v;v=next[u]; } printf("%lld\n%d",ans,ans1); }