Description
Gilbert is a gardener who loves planting flowers and trees. He also enjoys using tree data structures to solve programming problems, such as segment tree and treap. However, he recently felt that programming was too exhausting and decided to focus on gardening.
By chance, he planted an "expression tree" that only operates with operations: +, -, and *. He was excited to discover that each expression tree has its own beauty value, which depends on the outcome of the expression tree's calculation mod by 998244353 (the remainder when divided by 998244353, which is the % operator in C++). For example, the beauty of the expression tree "0 * (3 - 4)" is 0 % 998244353 = 0.
As a gardener, Gilbert wants to enhance the beauty of this expression tree. He plans to do this by selecting two nodes that do not have an ancestor-descendant relationship and swapping their subtrees. Since Gilbert is lazy, he hopes to perform this swap no more than once. However, he is unsure how to swap to maximize the overall beauty of the tree. He has asked for your help and will provide you with the preorder expression of this expression tree. Please tell him the highest possible beauty of the expression tree after performing at most one swap.
Example:
Choosing to swap the subtrees of these two nodes can maximize the beauty of the tree.
About mod operation with negative number: https://math.stackexchange.com/questions/2179579/how-can-i-find-a-mod-with-negative-number
Input
The first line of the input is an integer N(3 <= N <= 500), being the length of the prefix expression of the expression tree.
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.
Output
Output the maximum beautify of the expression tree after performing at most one swap.
Note that you should have a '\n' in the end.
Hint:
If you have no idea how to implement, please take it as your reference.
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define mod 998244353 // Define a modulo for the beauty calculation. // Define a node structure for the expression tree. typedef struct _Node { int val; // {0 ~ 9: number, -1: +, -2: -, -3: *} int ans; struct _Node *lc, *rc; // Left child, right child. } Node; char s[505] = {}; // Input string representing the preorder expression of the tree. Node *arr[505] = {}; // Array to store pointers to nodes for easy access. // Function to build the expression tree from the input string. Node *build() { } // Function to evaluate the expression tree and calculate its beauty. int eval(Node *r) { } // 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 an ancestor-descendant relationship. bool check(int a, int b) { } // Function to swap the subtrees rooted at nodes a and b. void swap(int a, int b) { } // Main function. int main() { }