错误代码AC:
#include<iostream>
#include<vector>
#define pii pair<int,int>
using namespace std;
int T,n,d[200005],dp[200005],ans;
vector <pii> a[200005];
void dfs(int p,int fa){
if(a[p].size()==1){
d[p]=a[p][0].second;
return;
}
for(int i=0;i<a[p].size();i++){
int nxt=a[p][i].first;
if(nxt!=fa){
dfs(nxt,p);
d[p]+=min(a[p][i].second,d[nxt]);
}
}
}
void dp1(int p,int fa){
// if(a[p].size()==1){
// dp[p]=d[p];
// return;
// }
for(int i=0;i<a[p].size();i++){
int nxt=a[p][i].first;
if(nxt!=fa){
if(a[p].size()==1)dp[nxt]=d[nxt]+a[p][i].second;
else dp[nxt]=d[nxt]+min(dp[p]-min(a[p][i].second,d[nxt]),a[p][i].second);
dp1(nxt,p);
}
}
}
int main(){
cin>>T;
while(T--){
cin>>n;
ans=-1;
for(int i=1;i<=n;i++){
a[i].clear();
d[i]=0,dp[i]=0;
}
for(int i=1;i<n;i++){
int x,y,z;
cin>>x>>y>>z;
a[x].push_back(make_pair(y,z));
a[y].push_back(make_pair(x,z));
}
dfs(1,0);
dp[1]=d[1];
dp1(1,0);
for(int i=1;i<=n;i++){
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
}
return 0;
}
在进行dfs时如果根度数为1是会出现错误,但是洛谷数据AC了,望加强