Guest User

Untitled

a guest
Oct 22nd, 2019
173
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. #pragma GCC optimize ("O3")
  3. #pragma GCC target ("sse4")
  4. */
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. typedef long long ll;
  9. const ll INF = 1e18;
  10. /*
  11. typedef long long ll;
  12. typedef long double ld;
  13.  
  14. #define mp make_pair
  15. #define pub push_back
  16. #define puf push_front
  17. #define pob pop_back
  18. #define pof pop_front
  19. #define ins insert
  20. #define f first
  21. #define s second
  22. #define lb lower_bound
  23. #define ub upper_bound
  24.  
  25. #define sz(x) (size_t)x.size()
  26. #define all(x) begin(x), end(x)
  27. #define rsz resize
  28.  
  29. const ll INF = 1e18;
  30. const ld PI = 4*atan((ld)1);
  31. const int MOD = 1e9 + 7;
  32.  
  33. #include <ext/pb_ds/assoc_container.hpp>
  34. #include <ext/pb_ds/tree_policy.hpp>
  35. using namespace __gnu_pbds;
  36. template <typename T>
  37. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  38. #define ook order_of_key
  39. #define fbo find_by_order
  40. */
  41.  
  42. int G[100000][2];
  43.  
  44. int addG(int a, int b){
  45.     if(G[a][1] == -1){
  46.         if(G[a][0] == -1)
  47.             G[a][0] = b;
  48.         else
  49.             G[a][1] = b;
  50.         return 0;
  51.     }
  52.     return -1;
  53. }
  54.  
  55. int main(){
  56.     int N;
  57.     cin >> N;
  58.    
  59.     ll cost[100000][3];
  60.     for(int i = 0; i < N; ++i)
  61.         cin >> cost[i][0];
  62.     for(int i = 0; i < N; ++i)
  63.         cin >> cost[i][1];
  64.     for(int i = 0; i < N; ++i)
  65.         cin >> cost[i][2];
  66.  
  67.     fill_n(*G, N*2, -1);
  68.     for(int i = 0; i < N-1; ++i){
  69.         int u, v;
  70.         cin >> u >> v;
  71.         --u, --v;
  72.         if(addG(u, v) || addG(v, u))
  73.             {cout << -1 << endl; return 0;}
  74.     }
  75.  
  76.     ll dp[100000][3][3];
  77.     int cur = 0, p1, p2;
  78.     while(G[cur][1] != -1)
  79.         ++cur;
  80.     for(int i = 0; i < 3; ++i)
  81.         for(int j = 0; j < 3; ++j)
  82.             dp[cur][i][j] = cost[cur][i];
  83.     p2 = -1;
  84.     p1 = cur;
  85.     for(int i = 0; i < N-1; ++i){
  86.         cur = G[cur][0] != p2 ? G[cur][0] : G[cur][1];
  87.         for(int j = 0; j < 3; ++j){
  88.             for(int k = 0; k < 3; ++k){
  89.                 if(j == k)
  90.                     continue;
  91.                 int tmp = 0;
  92.                 for(; tmp == j || tmp == k; ++tmp);
  93.                 dp[cur][j][k] = cost[cur][j] + dp[p1][k][tmp];
  94.             }
  95.         }
  96.         p2 = p1;
  97.         p1 = cur;
  98.     }
  99.    
  100.     ll ans = INF;
  101.     cur = 0;
  102.     int cols[100000];
  103.     for(int i = 0; i < 3; ++i){
  104.         for(int j = 0; j < 3; ++j){
  105.             if(i == j)
  106.                 continue;
  107.             if(dp[cur][i][j] < ans){
  108.                 ans = dp[cur][i][j];
  109.                 cols[N-1] = i;
  110.                 cols[N-2] = j;
  111.             }
  112.         }
  113.     }
  114.     for(int i = N-3; i >= 0; --i){
  115.         int tmp = 0;
  116.         for(; tmp == cols[i+1] || tmp == cols[i+2]; ++tmp);
  117.         cols[i] = tmp;
  118.     }
  119.  
  120.     cout << ans << endl;
  121.     for(int i = 0; i < N; ++i)
  122.         cout << cols[i] << " ";
  123.     cout << endl;
  124. }
  125. //Keep It Simple, Stupid!
RAW Paste Data