时间戳

首页 > 技术文章 > （树的重心/DFS/构造）AtCoder Grand Contest 018 D - Tree and Hamilton Path

（树的重心/DFS/构造）AtCoder Grand Contest 018 D - Tree and Hamilton Path

quintessence 2017-07-24 18:30 原文

D - Tree and Hamilton Path

Time limit : 2sec / Memory limit : 256MB

Score : 1100 points

Problem Statement

There is a tree with N vertices, numbered 1 through N. The i-th edge in this tree connects Vertices Ai and Bi and has a length of Ci.

Joisino created a complete graph with N vertices. The length of the edge connecting Vertices u and v in this graph, is equal to the shortest distance between Vertices u and v in the tree above.

Joisino would like to know the length of the longest Hamiltonian path (see Notes) in this complete graph. Find the length of that path.

Notes

A Hamiltonian path in a graph is a path in the graph that visits each vertex exactly once.

Constraints

  • 2≤N≤105
  • 1≤Ai<Bi≤N
  • The given graph is a tree.
  • 1≤Ci≤108
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

N
A1 B1 C1
A2 B2 C2
:
AN−1 BN−1 CN−1

Output

Print the length of the longest Hamiltonian path in the complete graph created by Joisino.

Sample Input 1

Copy
5
1 2 5
3 4 7
2 3 3
2 5 2

Sample Output 1

Copy
38

The length of the Hamiltonian path 5 → 3 → 1 → 4 → 2 is 5+8+15+10=38. Since there is no Hamiltonian path with length 39 or greater in the graph, the answer is 38.

Sample Input 2

Copy
8
2 8 8
1 5 1
4 8 2
2 5 4
3 8 6
6 8 9
2 7 12

Sample Output 2

Copy
132

依然是按照官方题解的做法写的。DFS的方法比较巧妙，c数组 按照DFS的“方向”，记录某一节点在该方向上（包括自身）所有后代节点个数。这样统计官方题解中的si就非常方便了。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <queue>
 8 #include <set>
 9 #include <map>
10 #include <list>
11 #include <vector>
12 #include <stack>
13 #define mp make_pair
14 #define MIN(a,b) (a>b?b:a)
15 //#define MAX(a,b) (a>b?a:b)
16 typedef long long ll;
17 typedef unsigned long long ull;
18 const int MAX=1e5+5;
19 const int INF=1e9+5;
20 using namespace std;
21 //const int MOD=1e9+7;
22 typedef pair<ll,int> pii;
23 typedef pair<ll,ll> pll;
24 const double eps=0.00000001;
25 ll n,an,m=INF;
26 vector<pll>edge[MAX];
27 ll c[MAX];
28 void calc(ll now,ll pre)
29 {
30     c[now]=1;
31     for(auto &X:edge[now])
32     {
33         ll to,val;
34         tie(to,val)=X;
35         if(to==pre)
36             continue;
37         calc(to,now);
38         c[now]+=c[to];
39     }
40 }
41 void solve(ll now,ll pre,ll len)//从pre连到now的一条长为len的边
42 {
43     an+=2*len*min(c[now],n-c[now]);
44     pll mx={-1,-1};//now的最大子树的节点数 及连向其的边的权值
45     for(auto &X:edge[now])
46     {
47         ll to,val;
48         tie(to,val)=X;
49         if(to==pre)
50             continue;
51         mx=max(mx,{c[to],val});
52     }
53     mx=max(mx,{n-c[now],len});
54     if(2*mx.first==n)
55         m=min(m,mx.second);
56     else if(2*mx.first<n)
57     {
58         for(auto &X:edge[now])
59             m=min(m,X.second);
60     }
61     for(auto &X:edge[now])
62     {
63         ll to,val;
64         tie(to,val)=X;
65         if(to==pre)
66             continue;
67         solve(to,now,val);
68     }
69 }
70  
71 int main()
72 {
73     scanf("%lld",&n);
74     for(ll i=1;i<n;i++)
75     {
76         ll A,B,C;
77         scanf("%lld%lld%lld",&A,&B,&C);
78         edge[A].push_back({B,C});
79         edge[B].push_back({A,C});
80     }
81     calc(1,0);
82     solve(1,0,0);
83     printf("%lld\n",an-m);
84  
85 }

 

推荐阅读