题意：有一棵带权树每个节点上住着一个人。人后需要让所有人交换房子，但是每个结点只住一个人。问你所有人最长走多少路。
思路：这里有一个贪心就是每条边的权值乘以两边结点少的那一边的两倍。然后就是dfs求出每个结点子树上有多少点这样n-dp[v]就是另一边的点了。注意longlong和手动加栈。
代码如下：
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-03-23 22:14 5 * Filename : hdu_chengdu1.cpp 6 * Description : 7 * ************************************************/ 8 9 #pragma comment(linker, "/STACK:1024000000,1024000000") 10 #include <iostream> 11 #include <cstdio> 12 #include <cstring> 13 #include <cstdlib> 14 #include <cmath> 15 #include <algorithm> 16 #include <queue> 17 #include <stack> 18 #include <vector> 19 #include <set> 20 #include <map> 21 #define MP(a, b) make_pair(a, b) 22 #define PB(a) push_back(a) 23 24 using namespace std; 25 typedef long long ll; 26 typedef pair<int, int> pii; 27 typedef pair<unsigned int,unsigned int> puu; 28 typedef pair<int, double> pid; 29 typedef pair<ll, int> pli; 30 typedef pair<int, ll> pil; 31 32 const int INF = 0x3f3f3f3f; 33 const double eps = 1E-6; 34 const int LEN = 100000+10; 35 vector<pii> Map[LEN]; 36 int n, depth[LEN], dp[LEN], edge[LEN][3]; 37 38 int dfs(int v, int f, int d){ 39 depth[v] = d; 40 int ret = 1; 41 for(int i=0; i<Map[v].size(); i++){ 42 if(Map[v][i].first!=f) ret+=dfs(Map[v][i].first, v, d+1); 43 } 44 dp[v] = ret; 45 return ret; 46 } 47 48 int main() 49 { 50 // freopen("in.txt", "r", stdin); 51 52 ios::sync_with_stdio(false); 53 int T, kase = 1, a, b, c; 54 cin >> T; 55 while(T--){ 56 for(int i=0; i<LEN; i++) Map[i].clear(); 57 cin >> n; 58 for(int i=0; i<n-1; i++){ 59 cin >> a >> b >> c; 60 a--;b--; 61 edge[i][0] = a;edge[i][1] = b;edge[i][2] = c; 62 Map[a].PB(MP(b, c)); 63 Map[b].PB(MP(a, c)); 64 } 65 dfs(0, -1, 0); 66 ll ans = 0; 67 for(int i=0; i<n-1; i++){ 68 a = edge[i][0]; b = edge[i][1]; 69 c = (depth[a] > depth[b] ? dp[a] : dp[b]); 70 ans += (min(c, n-c)*2*edge[i][2]); 71 } 72 cout << "Case #" << kase++ << ": "; 73 cout << ans << endl; 74 } 75 return 0; 76 }
