Guest User

Untitled

a guest
Jun 25th, 2013
446
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 100 * 1000 + 10;
  8.  
  9. vector<int> g[N], w[N];
  10. bool u[N];
  11. int cnt[N];
  12. int n;
  13. long long res;
  14.  
  15. void dfs(int v)
  16. {
  17.     u[v] = true;
  18.     for (int i = 0; i < g[v].size(); i++)
  19.     {
  20.         int to = g[v][i];
  21.         if (u[to])
  22.             continue;
  23.         dfs(to);
  24.         res += min(cnt[to], n - cnt[to]) * 2ll * w[v][i];
  25.         cnt[v] += cnt[to];
  26.     }
  27. }
  28.  
  29. void solve(int test)
  30. {
  31.     scanf("%d", &n);
  32.     for (int i = 0; i < n; i++)
  33.     {
  34.         g[i].clear();
  35.         w[i].clear();
  36.         u[i] = false;
  37.         cnt[i] = 1;
  38.     }
  39.     for (int i = 0; i < n - 1; i++)
  40.     {
  41.         int x, y, z;
  42.         scanf("%d%d%d", &x, &y, &z);
  43.         --x;
  44.         --y;
  45.         g[x].push_back(y);
  46.         g[y].push_back(x);
  47.         w[x].push_back(z);
  48.         w[y].push_back(z);
  49.     }
  50.     res = 0;
  51.     dfs(0);
  52.     printf("Case #%d: ", test);
  53.     printf("%lld\n", res);
  54. }
  55.  
  56. int main()
  57. {
  58.     int t;
  59.     scanf("%d", &t);
  60.     for (int i = 1; i <= t; i++)
  61.         solve(i);
  62.  
  63.     return 0;
  64. }
RAW Paste Data