Description
After extensive practice, Gilbert has finally become a Master Gardener.
Every expression tree he plants grows into a perfect shape. "Perfect" means that if the height of the tree is H, then the number of nodes in the tree is 2H+1 - 1. This kind of expression tree is referred to as a perfect expression tree. (Note that the height of the following example tree is 2 not 3.)
Although the shape of the expression trees Gilbert grows is perfect, but their beauty is still not up to his standards.
The beauty value depends on the outcome of the expression tree's calculation divided by 998244353.
Gilbert needs your help to enhance the beauty value of his expression tree. He will provide you with the height H of the expression tree, the query type T, and the preorder traversal of this expression tree. You need to answer Gilbert's query to help him.
- T = 1: Select two nodes that do not have an ancestor-descendant relationship and swap their subtrees.
- T = 2: Select two sibling nodes (having the same parent) and swap their subtrees.
- For a given query whose type can be T = 1 or T = 2, please output the highest possible beauty of the expression tree after performing at most one swap.
Note:
You may use the following formula to do required calculations:
((1ll * OPERAND1 OPERATOR OPERAND2) % mod + mod) % mod
Input
The first line contains two positive integers, H and T, representing the height of the expression tree and the type of query, respectively.
The next line is the expression tree (in prefix expression). The expression contains only +, -, * and digits. All the numbers in the expression are integers between 0 and 9.
It is guaranteed that the length of the expression is 2H+1 - 1.
Constraints
- For testcases 1 ~ 2: 1 ≤ H ≤ 6, T = 1
- For testcases 3 ~ 4: 1 ≤ H ≤ 20, T = 2, '-' operator ≤ 20
- For testcases 5 ~ 7: 1 ≤ H ≤ 20, T = 2
- For testcases 8 ~ 10: 1 ≤ H ≤ 10, T = 1
Output
Output the maximum beauty of the expression tree after performing at most one swap.
Note that you should have a '\n' in the end.
Hints
- For testcases 1 ~ 2: The approach for the corresponding practice problem is applicable.
- For testcases 3 ~ 4: The approach for testcases 1 ~ 2 is also applicable, but please find each pair of siblings "directly" and see when is necessary to recalculate the while tree for a possible better beauty value.
- For testcases 5 ~ 10: A more efficient approach is required.
You may consider to use the following reference code.
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define mod 998244353 // Define a modulo for the beauty calculation. typedef struct _Node { int val; // {0 ~ 9: number, -1: +, -2: -, -3: *} int ans; // evaluate result struct _Node *lc, *rc, *p; //Left child, Right child, Parent } Node; char expr[2200000] = {}; // Input string representing the preorder expression of the tree. Node *tree[2200000] = {}; // Array to store pointers to nodes for easy access. int h, t, n; int idx = 0; // Function to build the expression tree from the input string. Node *build() { if(idx >= n) return NULL; Node *r = (Node *)malloc(sizeof(Node)); tree[idx] = r; r->ans = -1, r->lc = r->rc = r->p = NULL; if(expr[idx] >= '0' && expr[idx] <= '9'){ r->val = expr[idx] - '0'; idx++; } else { if(expr[idx] == '+') r->val = -1; else if(expr[idx] == '-') r->val = -2; else r->val = -3; idx++; r->lc = build(); r->rc = build(); r->lc->p = r; r->rc->p = r; } return r; } // Function to evaluate the expression tree and calculate its beauty. int eval(Node *t) { } // Function to swap the subtrees rooted at nodes a and b. void swap(Node *a, Node *b) { } // Depth-First Search function to check if target node is in the subtree rooted at 'now'. bool dfs(Node *now, Node *target) { } // Function to check if two nodes have anancestor-descendantrelationship. bool check(Node *a, Node *b) { } int main() { scanf("%d %d", &h, &t); scanf("%s", expr); n = (1 << (h + 1)) - 1; // n = 2 ^ (h + 1) - 1 build(); int ans = eval(tree[0]); if(t == 1) { } else { } printf("%d\n", ans); }