牛客网小叶的日常巡查与维护

 1 #include 
 2 #include 
 3 #include 
 4 #include <string.h>
 5 #include 
 6 #include 
 7 #include 
 8 using namespace std;
 9 #define N 74444
10 typedef long long ll;
11 vectorint,ll> >g[N];
12 int lie;
13 ll sum[N],S;
14 void dfs(int fa,int now)
15 {
16     int len=g[now].size();
17     pair<int,long long>p;
18     for(int i=0;i)
19     {
20         p=g[now][i];
21         if(p.first!=fa)
22         {
23            sum[p.first]=sum[now]+p.second;
24            if(S<sum[p.first]){
25             lie=p.first;
26             S=sum[p.first];
27            }
28            dfs(now,p.first);
29         }
30     }
31 }
32 int main()
33 {
34     int n;
35     scanf("%d",&n);
36     for(int i=1;i)
37     {
38         int x,y;
39         long long v;
40         scanf("%d%d%lld",&x,&y,&v);
41         g[x].push_back(make_pair(y,v));
42         g[y].push_back(make_pair(x,v));
43     }
44     S=0;
45     dfs(0,1);
46     S=0;
47     memset(sum,0,sizeof(sum));
48     dfs(0,lie);
49     printf("%lld\n",S*10+(1+S)*S/2);
50     return 0;
51 }