fork download
copy 
  1. #include <bits/stdc++.h> 
  2. #define rep(i, n) for (int i = 0; i < (int)(n); ++ i) 
  3. #define rep1(i, n) for (int i = 1; i <= (int)(n); ++ i) 
  4. #define MP make_pair 
  5. using namespace std; 
  6. typedef long long LL; 
  7. typedef pair<int, int> PII; 
  8. const int INF = 1e9 + 7; 
  9. int N, K; 
  10. int d[205], dist[205][205]; 
  11. int f[205][205], g[205], cent[205]; 
  12. vector<int> G[205]; 
  13. void dfs_dist(int ori, int v, int par, int dis) 
  14. { 
  15.  dist[ori][v] = dis; 
  16.  rep(i, G[v].size()) { 
  17.  int u = G[v][i]; 
  18.  if (u == par) continue; 
  19.  dfs_dist(ori, u, v, dis + 1); 
  20.  } 
  21. } 
  22. void dfs(int v, int par = -1)
  23. { 
  24.  rep1(i, N) f[v][i] = d[dist[v][i]]; 
  25.  rep(i, G[v].size()) { 
  26.  int u = G[v][i]; 
  27.  if (u == par) continue; 
  28.  dfs(u, v); 
  29.  rep1(j, N) { 
  30.  f[v][j] += min(f[u][j], g[u]); 
  31.  } 
  32.  } 
  33.  g[v] = INF; 
  34.  rep1(i, N) { 
  35.  if (dist[v][i] < dist[par][i] + 1 && f[v][i] + K < g[v]) { 
  36.  g[v] = f[v][i] + K; 
  37.  cent[v] = i; 
  38.  } 
  39.  } 
  40. } 
  41. void dump(int v, int par, int centre) 
  42. { 
  43.  cent[v] = centre; 
  44.  rep(i, G[v].size()) { 
  45.  int u = G[v][i]; 
  46.  if (u == par) continue; 
  47.  dump(u, v, g[u] < f[u][centre] ? cent[u] : centre);}} 
  48. int main() 
  49. { 
  50. scanf("%d%d", &N, &K);d[0] = 0;rep1(i, N - 1)
  51.  scanf("%d", &d[i]);rep(i, N - 1)
  52.  { 
  53. int u, v; 
  54. scanf("%d%d", &u, &v); 
  55. G[u].push_back(v), G[v].push_back(u);} 
  56. rep1(i, N) dfs_dist(i, i, -1, 0); 
  57. dfs(1, 1); 
  58. printf("%d\n", g[1]); 
  59. dump(1, 1, cent[1]); 
  60. rep1(i, N) 
  61. printf("%d ", cent[i]); 
  62. printf("\n"); 
  63. return 0; 
  64. printf("void init()cin>>n>>k;"); 
  65. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000007
https://ideone.com/drJG77
language:
C++ (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!