样例是对的,但是交上去全WA
调了很久没调出来
我妙妙屋了(?)
#include <bits/stdc++.h>
using namespace std;
struct Node{
int bian,cnt;
};
vector<Node>g[500007];
int n,s,dp[500007],ans,anss;
void DFS(int now)
{
for(int i=0;i<g[now].size();i++)
{
int v=g[now][i].bian;
DFS(v);
dp[now]=max(dp[now],dp[v]+g[now][i].cnt);
}
ans=dp[now];
for(int i=0;i<g[now].size();i++)
{
int v=g[now][i].bian;
anss=anss+(ans-(g[now][i].cnt+dp[v]));
}
}
int main()
{
cin>>n;
cin>>s;
for(int i=1;i<n;i++)
{
Node _;
int tmp1;
cin>>tmp1>>_.bian>>_.cnt;
g[tmp1].push_back(_);
}
DFS(s);
cout<<anss;
return 0;
}
感觉没啥问题啊。。。