Advertisement
Guest User

Untitled

a guest
Dec 21st, 2021
500
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.43 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using lint = long long;
  5. const lint INF = 1e15;
  6.  
  7. int pathLength[155][155];
  8. int inPath[155][155][155];
  9. int freeEdge[155][155];
  10. lint dp[155][155][155][2][2];
  11.  
  12. void chmax(lint &a, lint b) {
  13.   a = max(a, b);
  14. }
  15.  
  16. void Main() {
  17.   int N;
  18.   cin >> N;
  19.   vector<lint> A(N);
  20.   for (int i = 0; i < N; i++) {
  21.     cin >> A[i];
  22.   }
  23.   vector<vector<int>> adj(N + 1);
  24.   for (int i = 0; i < N; i++ ){
  25.     int u, v;
  26.     cin >> u >> v;
  27.     u--, v--;
  28.     adj[u].emplace_back(v);
  29.     adj[v].emplace_back(u);
  30.   }
  31.  
  32.   for (int i = 0; i <= N + 3; i++) {
  33.     for (int j = 0; j <= N + 3; j++) {
  34.       freeEdge[i][j] = 0;
  35.       pathLength[i][j] = 0;
  36.       for (int k = 0; k <= N + 3; k++) {
  37.         inPath[i][j][k] = 0;
  38.         for (int a = 0; a < 2; a++) {
  39.           for (int b = 0; b < 2; b++) {
  40.             dp[i][j][k][a][b] = -INF;
  41.           }
  42.         }
  43.       }
  44.     }
  45.   }
  46.  
  47.   for (int i = 0; i <= N; i++) {
  48.     for (int j = 0; j <= N; j++) {
  49.       const auto Dfs = [&](const auto &self, int u, int p) -> bool {
  50.         if (u == j) {
  51.           inPath[i][j][u] = 1;
  52.           return true;
  53.         }
  54.         for (auto v : adj[u]) {
  55.           if (v != p) {
  56.             if (self(self, v, u)) {
  57.               pathLength[i][j] += 1;
  58.               inPath[i][j][u] = 1;
  59.               return true;
  60.             }
  61.           }
  62.         }
  63.         return false;
  64.       };
  65.       Dfs(Dfs, i, -1);
  66.       const auto Sub = [&](const auto &self, int u, int p) -> int {
  67.         int res = 1;
  68.         for (auto v : adj[u]) {
  69.           if (v != p) {
  70.             res += self(self, v, u);
  71.           }
  72.         }
  73.         return res;
  74.       };
  75.       for (int k = 0; k <= N; k++) if (k != i && k != j && inPath[i][j][k]) {
  76.         for (auto x : adj[k]) {
  77.           if (!inPath[i][j][x]) {
  78.             freeEdge[i][j] += Sub(Sub, x, k);
  79.           }
  80.         }
  81.       }
  82.     }
  83.   }
  84.  
  85.   for (int i = 0; i <= N; i++) {
  86.     dp[0][i][i][1][1] = 0;
  87.   }
  88.  
  89.   lint ans = -INF;
  90.   for (int pos = 0; pos <= N; pos++) {
  91.     for (int dx = 1; dx >= 0; dx--) {
  92.       for (int dy = 1; dy >= 0; dy--) {
  93.         for (int x = 0; x <= N; x++) {
  94.           for (int y = 0; y <= N; y++) {
  95.             if (dp[pos][x][y][dx][dy] < 0) {
  96.               continue;
  97.             }
  98.             if (pos == N && dx == 1 && dy == 1) {
  99.               ans = max(ans, dp[pos][x][y][dx][dy]);
  100.             }
  101.             if (pos == N) {
  102.               continue;
  103.             }
  104.             lint val = dp[pos][x][y][dx][dy];
  105.             if (dx == 0) {
  106.               chmax(dp[pos + 1][x][y][1][dy], val + A[pos]);
  107.             } else {
  108.               for (auto nxtx : adj[x]) if (!inPath[x][y][nxtx]) {
  109.                 chmax(dp[pos][nxtx][y][0][dy], val);
  110.               }
  111.             }
  112.             if (dy == 0) {
  113.               chmax(dp[pos + 1][x][y][dx][1], val + A[pos]);
  114.             } else {
  115.               for (auto nxty : adj[y]) if (!inPath[x][y][nxty]) {
  116.                 chmax(dp[pos][x][nxty][dx][0], val);
  117.               }
  118.             }
  119.             int unused = pathLength[x][y] - (dx == 0) - (dy == 0) + freeEdge[x][y];
  120.             unused -= pos;
  121.             if (unused >= 1) {
  122.               chmax(dp[pos + 1][x][y][dx][dy], val);
  123.             }
  124.           }
  125.         }
  126.       }
  127.     }
  128.   }
  129.   cout << ans << '\n';
  130. }
  131.  
  132. int main() {
  133.   ios::sync_with_stdio(0);
  134.   cin.tie(0);
  135.  
  136.   int T;
  137.   cin >> T;
  138.   while (T--) {
  139.     Main();
  140.   }
  141.   return 0;
  142. }
  143.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement