text:
# Dynamic programming on trees with minimal memory

Dynamic programming on trees has always been a beloved topic of mine. I think it nicely teaches fundamental principles of DP and recurrence, at least on a theoretical level. But in practice, when one has to implement a concrete program using DP on trees, there are some traps which have to be avoided. For instance, one has to be aware of the fact that usually such a program consumes pretty decent amount of memory. Asymptotically it is linear on the number of vertices in the tree, but the constant could be quite big. In this article we will show how much of this memory is really necessary when programming in C++, the most used language in programming competitions.

We will illustrate it with a classic problem of counting the number of maximum-size matchings in an undirected tree. There is nothing special about this particular problem, apart from the fact that I like it and it has nice educational properties – it is not very complicated, but at the same time no trivial and it nicely exemplifies what we can expect from DP on trees. Therefore most of the things we say here can be applied to other DP on trees (maybe except the very last bits, in which we will use some features of this particular problem). Especially the part dealing with reading a tree from the input to the memory is universal and interesting all by itself.

This article features task Matchings that I have prepared for Polish Olympiad in Informatics Training Camp in 2010 and used once more at Brazilian ICPC Summer School in 2015. It is significantly expanded version of a lecture I gave at the latter camp.

## Definition of the problem and DP recurrences

You can try solving problem Matchings from Polish Olympiad in Informatics Training Camp 2010.

We are given an undirected tree which has $n$ vertices and $n-1$ edges. A matching is a subset of edges in which every vertex is adjacent to at most one edge from the subset. The size of a matching is the number of edges in this subset. We want to calculate the maximum size of a matching and also the number of matchings of this size. The size of a matching is limited by $\frac{n}{2}$, since each edge in a matching “uses” two vertices. However, the number of matchings can be exponential (in a star-shaped tree where each ray has three vertices, there are $\frac{n}{3} 2^{n/3}$ matchings), so we use a standard trick and ask for this number modulo given integer $M$.

The DP solution for this problem is not very hard. As usual, we pick an arbitrary vertex $v_\star$ and make it a root of the tree, then we direct every edge to make a directed tree. Finally we traverse this tree from leaves to the root, performing some calculations for every vertex $v$ based on calculations done previously for its children $u_0, \ldots, u_{m-1}$.

### Finding the maximum size

First, let's concentrate on finding the maximum size. We will proceed bottom-up and for every vertex $v$ we will calculate the maximum size of a matching in a subtree rooted in vertex $v$. In fact we will calculate two values: $dt[v]$ – the maximum size of a matching in the subtree which uses vertex $v$, i.e. there is an edge $vu_i$ for some $i$ in the matching, and $dn[v]$ – the maximum size of a matching in the subtree which does not use vertex $v$, i.e. there is no such edge.

The recurrence for these values is as follows. When the matching does not use vertex $v$, all its children $u_i$ are free to be used (or not) in their respective subtrees which can be considered independently. Thus it is:

$dn[v] = \sum_{i} \max(dt[u_i], dn[u_i])$

For case when the matching uses vertex $v$, we have to decide which edge $vu_i$ goes into the matching. Then in the subtree rooted in $u_i$ we cannot use this vertex, since it is already matched with its parent. Of course we use the edge which results in a matching of the largest size. Therefore

$dt[v] = \max_{i} (1 + dn[u_i] + \sum_{j \neq i} \max(dt[u_j], dn[u_j]))$

We assume that sum over empty set is $0$, and max over empty set is $-\infty$, thus for a leaf $v$ we have $dn[v] = 0$ and $dt[v] = -\infty$. The above formula for $dt[v]$ is not very efficient, since it calculates sums over vertices many times. It is better to calculate the sum once (and in fact this is exactly what we have done in $dn[v]$), and then remove one element from it:

$dt[v] = dn[v] + \max_{i} (1 + dn[u_i] - \max(dt[u_i], dn[u_i]))$

Now calculating $dn[v]$ and $dt[v]$ takes linear time in number of children of vertex $v$, therefore calculating these values for all vertices takes $O(n)$.

We can simplify these formulas a little bit. Assume that for some vertex $v$ we have $dn[v] \geq 0$, therefore there is a non-empty matching which does not use $v$. If we consider a matching of maximum size and a top-most vertex which is matched in it by some edge, we can (since vertices above it are not used) move this edge to the top, so vertex $v$ will be used by it. Thus we have $dt[v] \geq dn[v]$. On the other hand if $dn[v] = 0$, then either $v$ is a leaf (and then $dt[v] = -\infty$) or $dt[v] \geq 1$. So let's fix the definition of $dt[v]$ to be $0$ in case when $v$ is a leaf. Thanks to that change we will always have $dt[v] \geq dn[v]$, thus $dt[v] = \max(dt[v], dn[v])$ and the formulas become:

$dn[v] = \sum_{i} dt[u_i]$

$dt[v] = dn[v] + \max_{i} (1 + dn[u_i] - dt[u_i])$

And for leaves we have $dn[v] = dt[v] = 0$.

### Finding the number of maximum-size matchings

Now let's proceed to counting the matchings. Again, for every vertex $v$ we introduce two variables $cn[v]$ and $ct[v]$ – the numbers of maximum-size matchings in subtree $v$ which (do not) use vertex $v$. We also use notation $c[v]$ to denote a number of maximum-size matchings in the subtree, regardless of situation of vertex $v$. Since $dt[v] \geq dn[v]$, then $ct[v]$ is always included, but we include $cn[v]$ only if $dn[v]$ is equal to $dt[v]$:

$c[v] = ct[v] + cn[v] \cdot [ dn[v] = dt[v] ]$

For $cn[v]$, that is when calculating number of maximum-size matchings which do not use vertex $v$, we independently consider all subtrees rooted in children of vertex $v$, so we just take a product of numbers of all maximum-size matchings in these subtrees:

$cn[v] = \prod_{i} c[u_i]$

For calculating $ct[v]$ we must iterate over each possible edge $vu_i$, and see whether the maximum size of a matching using this edge equals to $dt[v]$. In case the answer is positive, we replace $c[u_i]$ with $cn[u_i]$ in already calculated product $cn[v]$ (because we do not want to recalculate the product again), and finally take a sum of such products:

$ct[v] = \sum_{i} ( cn[v] / c[u_i] \cdot cn[u_i] ) \cdot [ dt[v] = dn[v] + 1 + dn[u_i] - dt[u_i] ]$

Unfortunately, there is a slight problem with the above formula – we cannot perform division. It would be perfectly fine, if we had worked with numbers in full precision, since $c[v]$ is never equal to $0$ and we can do normal division. But since we are working with numbers modulo $M$, we have to multiply by inversion, and $c[u_i]$ could simply evaluate to $0$ modulo $M$. (And if $M$ was not a prime number, even more numbers wouldn't have their inversions.)

Therefore we need to use a slightly different approach, but since it is a little bit technical, we will postpone it to a later part of the article. For now just suppose that it can be done, in linear time and with no additional memory.

If vertex $v_\star$ is the root of the tree, then numbers $dt[v_\star]$ and $c[v_\star]$ are the final answer to the problem. Therefore, we have an algorithm which solves the problem in optimal time $O(n)$ and memory complexity $O(n)$. To be more precise, dynamic programming calculations use four variables per vertex, making in a total of $4n$ variables.

## The standard approach for implementation

We will make some assumptions on implementation. We assume that the standard integer type int is big enough to hold numbers $2n$ and $M-1$, but not necessarily bigger. We also assume that all pointers to the memory are of the same size as this int. The codes below will be written in C++ with the help of one macro:

#include <algorithm> #include <cstdio> #include <vector> using namespace std; #define REP(i,n) for(int i=0;i<(n);++i)

We assume that all global variables and arrays are initialized to $0$.

The implementation consists of two phases: reading the description of the tree from the standard input, and traversing the tree and performing DP calculations.

First we need to know how the tree is given in the input. The most common way for specifying graphs (and trees in particular) is by listing their edges. More precisely, first we number vertices of the tree (e.g. using integers from $0$ to $n-1$), and then we put number $n$ in the input, followed by $n-1$ pairs $a, b$ which mean that vertex number $a$ is adjacent to vertex number $b$. Note that we number vertices only for convenience of such representation. We do not care that a particular vertex has some particular number.

The easiest way to input such a tree is to create for each vertex a vector $adj[v]$ which will store all vertices adjacent to $v$. The code is as follows:

const int N = 1000000; int n; vector<int> adj[N]; void load_tree() { scanf("%d", &n); REP(i, n-1) { int a, b; scanf("%d%d", &a, &b); adj[a].push_back(b); adj[b].push_back(a); } }

The whole tree is defined in the input using about $2n$ ints (to be precise one int to describe the size and $2n-2$ ints to describe edges, but we will ignore additive constants here). Let's calculate how much memory does it need.

We have $n$ vectors, each consists of three pointers: start of the allocated buffer (pointer begin), one place after the last element in the buffer (pointer end), and one place after the allocated buffer (pointer capacity). Thus the length of the allocated buffer and the amount of filled the buffer are represented as differences between pointers capacity and end with the pointer begin. As we have assumed in the beginning, the pointers and integers have the same size, so we need $3n$ ints just for storing vectors (even when they are empty).

So what happens if we read a tree? On the first push_back to each vector, it will allocate a buffer of size $1$, and every time if current buffer is completely filled, it will reallocate it to a buffer twice as big. So sum of these buffers will need at least $2n$ int to store all values, but most probably more, because of unused reserved space. In worst-case it could be as big as $4n$ ints, e.g. for a star-shaped tree with one vertex $v$ of degree $n-1$ and $n-2$ being a power of two. The last push_back to $adj[v]$ will result in a vector of size $2n-4$ which during reallocating must coexist in memory with the old vector of size $n-2$, and of course we need $n-1$ ints for the one-element vectors for all the other vertices.

But that is not everything. What could be not obvious is that vector when allocating a buffer calls system function malloc which needs some memory to somehow keep track of all these allocated buffers. How much it depends on the implementation (and other factors such as memory alignment), but for sure it needs at least one pointer or pointer-size int, so let's assume that. That gives us another $n$ ints.

In summary: just to read the tree in the memory using vectors we need $6n$ ints, possibly more (even up to $8n$ ints).

### Calculating DP

Having read the tree we want to calculate the variables defined by DP recurrences. Again, the easiest way to do this is to make a DFS search through the tree starting from an arbitrary root, let's say $v_\star = 0$. We should track from which vertex we entered vertex $v$, so we will know which vertex from $adj[v]$ is the parent of $v$; the rest of them are its children. During the search we can calculate all DP arrays:

/* Recurse on node v with parent par (-1 if v is the root). */ void recursive_dp(int v, int par) { for (vector<int>::iterator it = adj[v].begin(); it != adj[v].end(); ++it) { const int u = *it; if (u != par) { recursive_dp(u, v); /* DP arrays for node u has been updated. */ /* Do something with edge from v to u, if needed. */ } } /* Update DP arrays for node v. */ update_v(v, par); } recursive_dp(root, -1);

The above code is quite general, and below is a function which calculates arrays dn and dt for our specific problem (we won't show yet how to calculate arrays cn and ct due to a problem with division mentioned before).

int dn[N], dt[N], cn[N], ct[N]; void update_v(int v, int par) { for (vector<int>::iterator it = adj[v].begin(); it != adj[v].end(); ++it) { const int u = *it; if (u == par) continue; dn[v] += dt[u]; dt[v] = max(dt[v], 1 + dn[u] - dt[u]); } dt[v] += dn[v]; }

This is the second phase: dynamic programming. Memory used by this phase can be divided into two parts: memory used by the DP arrays and memory used in order to traverse the tree. Let's calculate the latter. Since we are using recursion, we need to know how it's implemented by the compiler. There will be frames on the stack, each contains at least: return address, function arguments, and local variables. Return address is a pointer and in our case we have two arguments (v, par) and one local variable (it, which is iterator, thus can be implemented as a simple pointer). That's four ints in one frame. In the worst case our tree could be just a long path (so will be of depth $n$), thus the stack could contain $n$ frames, and will need $4n$ ints.

Actually it could be worse, since we do not know exactly what is inside the stack frame, until we dive into assembly. It is not uncommon to have there a pointer to the previous stack frame, temporary local variables (used to calculate values of subexpressions in complex expressions). Moreover, on certain architectures stack frames must be aligned to certain boundaries. So we state that we need at least $4n$ ints, but the reality could be much worse.

To sum up both phases of the algorithm, we need at least $6n$ ints (probably more) for storing the tree, $4n$ ints (probably more) for traversing it, and additional $4n$ ints for storing DP arrays. That is at least $14n$ ints for solving the task. Can you guess now how much this can be improved?

I just say: a lot. But I won't disclose precisely how much, I think it is more fun to unwind it step by step.

So let's begin.

## Replacing things we cannot control

The saddest part of the above estimates is that we said we need at least but probably more. First, we try to get rid of sources of this uncertainty: vectors with malloc (which were used for reading and storing the tree) and recursion (which was used for DP calculations).

### Replacing vectors

One clear redundancy with malloced vectors is that both malloc and vector store the length of allocated buffers. Since we cannot change the behavior of vector class (at least not without creating custom allocators which is not what I would like to do here), perhaps we can somehow manage without it. Which leads to a question: why do we need vectors in the first place? The problem is that we need vectors to store adjacency lists for vertices, but since we are loading edges one by one, we do not know beforehand, how much vertices will go to each list. Thus we need some kind of structure which will be resizable, and vectors look like the natural choice here.

But maybe vectors are not the best choice to store adjacency lists? Maybe real lists would fit better? Since list support push_back operation, then we only have to change declaration to list<int> adj[N];.

Memory calculation: each element of the list, apart from the value (int) stores two pointers to the previous and to the next element on the list (list is doubly-linked) – three ints in total. Moreover, each time we insert a new element, new memory for this single element is malloced, which results in at least one more int for malloc bookkeeping. There will be $2n$ elements in all lists, so the total memory consumption would be at least $8n$ ints. It's even bigger than the lower bound for vectors.

Of course, we don't need doubly-linked lists. We can use just fine forward_list<int> class, and replace push_back operations with push_front (since the actual order of vertices on lists is not important for us). That will leave us with at least $6n$ ints, and part of this memory still goes to malloc bookkeeping. It's some improvement over vectors, but not much (only over their upper bound).

Let's try a different approach. We wouldn't need vectors if we know the size of each adjacency list. Actually we could get this information, if we could go twice through the input:

int n, deg[N], ptr[N]; int* adj[N]; void load_tree_2() { scanf("%d", &n); REP(i, n-1) { scanf("%d%d", &a, &b); deg[a]++; deg[b]++; } REP(i, n) { adj[i] = new int[deg[i]]; ptr[i] = 0; } /* Rewind the input file */ lseek(0); scanf("%d", &n); REP(i, n-1) { scanf("%d%d", &a, &b); adj[a][ptr[a]++] = b; adj[b][ptr[b]++] = a; } }

For each vertex $v$ we first calculate its degree $deg[v]$, which is exactly the number of vertices in its adjacency list. After that we malloc a correctly-sized buffer $adj[v]$. Then we rewind the file, and read it once more, and now we store vertices in the arrays. Index $ptr[v]$ will keep track of where to put the next value in this array.

That gives us $3n$ ints for arrays deg, ptr and adj and at least another $n$ ints for malloc bookkeeping. And sum of buffer lengths is $2n$ ints, thus we need $6n$ ints here, same as lists. But we can make a clever trick here. Each time we put a vertex number during the second phase, we can advance pointer adj, so we do not need array ptr. If we need original beginnings of buffers, we can just subtract their lengths. Thus the code for the part after rewinding the input file is:

scanf("%d", &n); REP(i, n-1) { scanf("%d%d", &a, &b); *(adj[a]++) = b; *(adj[b]++) = a; } REP(i, n) { adj[i] -= deg[i]; }

Then the code to iterate over adjacency list of $v$ is as follows:

for (int it = 0; it < deg[v]; ++it) { const int u = adj[v][it]; /* Do something with edge from v to u. */ }

This uses only $5n$ ints for reading the tree. Unfortunately in many contests we load the data from the standard input, so we can only read it once. Thus this approach will not work, but it's good to know it anyhow. But don't throw away above code. If we cannot read list of edges twice, we can just store it using additional $2n$ ints:

int n, a[N], b[N], deg[N]; int* adj[N]; void load_tree_2() { scanf("%d", &n); REP(i, n-1) { scanf("%d%d", &a[i], &b[i]); deg[a[i]]++; deg[b[i]]++; } REP(i, n) { adj[i] = new int[deg[i]]; } REP(i, n-1) { *(adj[a[i]]++) = b[i]; *(adj[b[i]]++) = a[i]; } REP(i, n) { adj[i] -= deg[i]; } }

This approach needs $7n$ ints for reading the tree. It's certainly better than upper bound for vectors, but approach with lists gave us $6n$ ints. But the above code has one big advantage: we do need $7n$ ints for the reading phase, but after that phase we only need $5n$ ints, since arrays a and b will no longer be needed and can be reused for different purposes. That is why, from now on, we will specify memory requirements of the first phase using two numbers: memory needed to store the tree after the phase plus additional memory needed for actually performing the phase. In this notation the last approach needs $(5+2)n$ ints.

### Replacing malloc

The above approach still uses malloc. It is wasteful, since we do not control memory used by malloc, but moreover we know that it at least uses $n$ ints for keeping track of lengths of reserved buffers, and we also redundantly do it in array deg. Instead of malloc we will keep all adjacency lists in one array Adj of length $2n$:

int n, a[N], b[N], deg[N+1], Adj[2*N]; void load_tree_2() { scanf("%d", &n); REP(i, n-1) { scanf("%d%d", &a[i], &b[i]); deg[a[i]]++; deg[b[i]]++; } REP(i, n) { deg[i+1] += deg[i]; } REP(i, n-1) { Adj[--deg[a[i]]] = b[i]; Adj[--deg[b[i]]] = a[i]; } }

The idea is that the subsequent lists are stored after each other in Adj. After the second loop value $deg[v]$ stores the index after the last element of adjacency list of $v$. Therefore after the third loop each $deg[v]$ stores the beginning. That is why the better name for this array after the load code is begin. Since it will be quite common for us to reuse memory for different purposes, we will use aliases for clarity:

int* begin = deg;

Note that array begin has length $n+1$, since it has to store the end of the array Adj in the last element. That is how to iterate over adjacency list of $v$:

for (int it = begin[v]; it < begin[v+1]; ++it) { const int u = Adj[it]; /* Do something with edge from v to u. */ }

In this approach we need $5n$ ints for all arrays, but after that only deg and Adj are used, so it's just $3n$ ints. In total memory consumption for this phase is exactly $(3+2)n$ ints tops, which is clearly better than the first approach with vectors (even if we do not care to reuse arrays a and b).

### Replacing recursion

As we said before, recursion costs us at least $4n$ ints, but in practice it could be much worse. We pay all this just for the convenience that recursive programs are slightly easier to write, but for just a little more programming work we can rewrite the function in iterative way, and get rid of the most of this overhead. Let's see what data from the stack frame is essential: actually it's only vertex number v and iterator it. Observe that the second argument par is just a copy of v from the previous frame, and since recursive_dp function (apart from the call in main) is only called in one place, thus return addresses in all frames (except the first) will be the same. Clearly this is a lot of wasted space, which would not be wasted if we write it by hand.

So as a start, let's just translate this function in an iterative way:

int qe, q[N]; vector<int>::iterator it[N]; void iterative_dp(int root) { qe = 0; q[qe++] = -1; /* Sentinel */ q[qe++] = root; REP(i, n) { it[i] = adj[i].begin(); } while (qe > 1) { const int v = q[qe-1], par = q[qe-2]; if (it[v] == adj[v].end()) { /* Update DP arrays for node v. */ update_v(v, par); /* Do something with edge from par to v. */ qe--; } else { const int u = *it[v]++; if (u != par) { q[qe++] = u; } } } }

As we can see, we only use LIFO queue q (which replaces stack) and array it, so indeed we have managed to do DP traversal in memory of $2n$ ints. Of course, in the previous section we replaced vectors with array Adj. We can therefore rewrite this:

int ptr[N]; ... ptr[i] = begin[i]; ... if (ptr[v] == begin[v+1]) { ... const int u = Adj[ptr[v]++];

Finally we have a new solution without vectors, malloc and recursion. Since the first phase used $(3+2)n$ ints of memory and in the second phase we use $2n$ ints for tree traversal, in total we use $5n$ ints. Adding $4n$ ints for DP arrays we got $9n$ ints, which is slightly less than two-thirds of memory usage for the first solution. But this is just a warm-up.

## Compressing the tree

In the previous section we took a standard implementation of a standard approach and got rid of unnecessary memory allocated by parts of the code we didn't have control over (library and compiler code). Now when dust have settled after we squeezed the standard implementation, let's take a closer look at the standard approach we are using. Maybe here we also have some room for improvement?

We specifically focus on a format in which we store the tree in memory in order to make a DP traversal over it.

### Remove pointers to parents

For every vertex $v$ we store its adjacency list, that is a list of all vertices incident to it. But the DP calculations are done over a rooted tree in which one of this incident vertex becomes a parent of vertex $v$. Luckily, we enter $v$ from this parent, so we can skip it while iterating over adjacency list of $v$. But since the existence of these parents in adjacency lists is only a nuisance, why don't we remove all of them before calculating DP? Since there are $n-1$ parent elements in all lists, this removal would shorten array Adj by half!

This can be accomplished by another DFS traversal over tree (performed before DP calculations) during which for each non-root vertex $v$ we copy last element of its adjacency list in the position of parent element on this list:

void remove_parents(int root) { qe = 0; q[qe++] = -1; q[qe++] = root; REP(i, n) { ptr[i] = begin[i]; } while (qe > 1) { const int v = q[qe-1], par = q[qe-2]; if (ptr[v] == begin[v+1] - (par != -1)) { qe--; } else { const int u = Adj[ptr[v]]; if (u == par) { Adj[ptr[v]] = Adj[begin[v+1] - 1]; } else { q[qe++] = u; ptr[v]++; } } }

Next we can safely remove the last elements from all non-root adjacency lists. That means that we must move elements on adjacency list of vertex $v$ by $v-1$ or $v$ positions to the left, depending whether number $v$ is greater than $v_\star$ or not:

REP(v, n) { const int shift = v - (v > root); for (int it = begin[v]; it < begin[v+1]; ++it) { Adj[it - shift] = Adj[it]; } begin[v] -= shift; } begin[n] -= n-1; }

After such transformation we no longer have to check for parents during DP tree traversal. But what's even more important, the second half of array Adj is no longer needed and its $n$ ints can be reused. To be able to reuse only part of some array, we can make one big array array holding all the memory we need to reuse, and make aliases inside this array, e.g. like this:

int array[5*N+1], dt[N], cn[N], ct[N]; int* a = array; int* b = array + N; int* Adj = array + 2*N; int* deg = array + 4*N; int* q = array; int* ptr = array + N; int* dn = array + 3*N;

Just remember to initialize the array with zeros, if it comes from reused space.

Thanks to that the first phase uses memory of $(2+3)n$ ints. Adding $2n+4n$ ints for the second phase, we get $8n$ ints for the whole program.

### Changing order of DP computations

Observe that we can perform DP calculations in any order, as long as calculations for every child of given vertex $v$ is performed before calculations for vertex $v$. In functions recurrence_dp and iterative_dp we have done it using DFS traversal, since we at the same time needed to know the parents of vertices. But now, after removing parents, we can also traverse vertices in BFS manner if we please:

int qb, qe, q[N]; q[qe++] = root; while (qb != qe) { const int v = q[qb++]; for (int it = begin[v]; it < begin[v+1]; ++it) { q[qe++] = Adj[it]; /* Fill array q */ } }

This code fills the array $q$ of size $n$ with BFS order of visiting vertices in the tree. Note that in the loop we no longer have access to the parent of $v$, but we don't need it. One important property of this order is that vertex $v$ is in array q before each of its children. Therefore we can make DP traversal on the tree using only arrays Adj, begin and q. We iterate over vertices from q in reversed order:

REP(i, n) { const int v = q[n-1 - i]; for (int it = begin[v]; it < begin[v+1]; ++it) { const int u = Adj[it]; /* Do something with edge from v to u. */ } }

Therefore in order to traverse the tree in the second phase we can use BFS order in array q, instead of stack in array q and array ptr. Thanks to that we only need $n+4n$ ints for the second phase, thus $7n$ ints for the whole solution (half of memory usage of the standard approach).

### Remove vertex numbers

All of this work we have done during reading the tree was about finding the correct order of vertices. We hinted before that the actual number of vertices do not matter – the only thing that matters is the shape of the tree. So wouldn't it be nice if the vertices were numbered in the input in some sensible order, for example in the BFS order we calculated in the previous section? But since they aren't, maybe we can renumber them?

The idea is as follows. The array q contains numbers of vertices in the BFS ordering. Therefore the $i$-th node (zero-based) in this ordering has number $q[i]$. We would like to change number of this node to simply $i$. We store node numbers in array Adj and they are also used as indices to array begin.

First, let's look how would array begin look like after doing such renumbering. We can do it by restoring degrees of all vertices in BFS order (and storing them in array newdeg), and once more transforming it into array begin:

int* newdeg = array + N; REP(i, n) { const int v = q[i]; newdeg[i] = begin[v+1] - begin[v]; } begin[0] = 0; REP(i, n) { begin[i+1] = begin[i] + newdeg[i]; }

It looks like we would have more problems with array Adj, since the vertices' numbers in it should be renumbered according to q, but also we should move blocks in this array according to changes in begin. But it would turn out, that new array Adj became trivial. Look closely how array q was constructed in the first place. We iterated through subsequent vertices in BFS order, so subsequent cells of Adj (after renumbering) must be equal to subsequent cells of q (except the first element of q which corresponds to the root of the tree). Therefore $Adj[i] = i+1$ for all $i$.

Since we don't need q too (because it's also trivial after renumbering), we only need temporary array of $n$ ints to store newdeg. Therefore new code for DP computation doesn't use q and Adj:

REP(i, n) { const int v = n-1 - i; for (int it = begin[v]; it < begin[v+1]; ++it) { const int u = it + 1; /* Do something with edge from v to u. */ } }

Wow. We have just compressed the whole information about the tree in just one array begin of size $n$. Moreover having just this array we can perform DP traversal over the tree. That's something. Therefore the first phase costs us $(1+4)n$ ints. And we don't need any additional memory for traversing the tree in the second phase, so it's just $4n$ ints of DP arrays. In total our solution uses $5n$ ints.

### Simpler method of compressing the tree

Actually, when we know that we can represent the whole tree using only one array begin, we can calculate this array even simpler. The process is as follows: we renumber the vertices in the tree in the BFS order, and then we create array deg which contains degrees of vertices in this BFS order. From array deg we retrieve new begin using standard method.

We start from our representation before doing any tree compression, thus from array Adj of size $2n$ (containing parents) and array with indices, which we call oldbegin for clarity. We will use an array q for queue (which will be reused for storing the degree of each vertex popped from the queue) and array vis for storing visited vertices (so we don't visit parents during BFS traversal):

int* oldbegin = begin; int* vis = array + N; qb = qe = 1; q[qe++] = root; REP(i, n) { vis[i] = false; } vis[root] = true; while (qb != qe) { const int v = q[qb]; q[qb++] = oldbegin[v+1] - oldbegin[v] - (v != root); for (int i = oldbegin[v]; i < oldbegin[v+1]; ++i) { const int u = Adj[i]; if (!vis[u]) { q[qe++] = u; vis[u] = true; } } } begin = q; begin[0] = 1; /* Shift by 1, since Adj[i] = i+1 */ REP(i, n) { begin[i+1] += begin[i]; }

At the end we only need array begin. Thus the cost of the first phase is $(1+4)n$ ints.

So with the compression of the tree the whole problem can be solved in just $5n$ ints, a little bit over one-third of original $14n$. We won't gain much improving the first phase, as long as DP arrays will need $4n$ ints, so let's switch back to DP calculations performed by our solution, to see if we can improve that.

## Improving DP calculations

First we keep the promise of showing how to calculate value of $ct[v]$ without division. Then we try to reduce the memory needed by DP calculations.

### Finishing finding the number of maximum-size matchings

Remember, that in formula for $ct[v]$ we used $cn[v] / c[u_i]$ to calculate a product of values $c[\cdot]$ for all children except $u_i$:

$c[u_0] \cdot c[u_1] \cdot \ldots \cdot c[u_{i-1}] \cdot c[u_{i+1}] \cdot c[u_{i+2}] \cdot \ldots \cdot c[u_{m-1}]$

Such approach worked fine with sum (because we could use subtraction), but with multiplication without ability to do division it does not work. However, we can solve it by calculating prefixes and suffixes as follows:

$cnl[i] = c[u_0] \cdot c[u_1] \cdot \ldots c[u_{i-1}]$

$cnr[i] = c[u_{i+1}] \cdot c[u_{i+2}] \cdot \ldots c[u_{m-1}]$

And then use the equality $cn[v] / cn[u_i] = cnl[i] \cdot cnr[i]$. The arrays cnl and cnr are calculated as follows:

$cnl[0] = 1;\quad cnl[i] = cnl[i-1] \cdot c[u_{i-1}]$

$cnr[m-1] = 1;\quad cnr[i] = c[u_{i+1}] \cdot cnr[i+1]$

So we are ready to present full C++ code of DP calculations. The first loop calculates arrays dn and dt in the same manner as before (we only use array begin rather than vectors). The second loop calculates helper arrays cnl and cnr. Finally, the third loop calculates arrays cn and ct. For clarity, we don't include taking modulo $M$ in the code.

int cnl[N], cnr[N]; void iterative_dp_2() { REP(i, n) { const int v = n-1 - i; dn[v] = 0; dt[v] = 0; for (int it = begin[v]; it < begin[v+1]; ++it) { const int u = it; dn[v] += dt[u]; dt[v] = max(dt[v], 1 + dn[u] - dt[u]); } dt[v] += dn[v]; } REP(i, n) { const int v = n-1 - i; const int m = begin[v+1] - begin[v]; cnl[0] = 1; cnr[m-1] = 1; for (int i = 0; i < m-1; ++it) { const int ul = begin[v] + i; const int cul = ct[ul] + cn[ul] * (dn[ul] == dt[ul]); cnl[i+1] = cnl[i] * cul; const int ur = begin[v+1]-1 - i; const int cur = ct[ur] + cn[ur] * (dn[ur] == dt[ur]); cnr[m-2-i] = cur * cnr[m-1-i]; } cn[v] = 1; ct[v] = 0; for (int it = begin[v]; it < begin[v+1]; ++it) { const int u = it; const int i = it - begin[v]; const int cu = ct[u] + cn[u] * (dn[u] == dt[u]); cn[v] *= cu; ct[v] += cnl[i] * cn[u] * cnr[i] * (dt[v] == dn[v] + 1 + dn[u] - dt[u]); } } }

Unfortunately, we need additional memory to store arrays cnl and cnr. These are arrays of size $m$, since they are only used for calculations for one vertex, but maximal $m$ can be as large as $n-1$. Therefore we need additional $2n$ ints, which is not good.

So let's take a closer look at the formula for $ct[v]$. It has a form:

$\sum_{0 \leq i < m} a_{0} \cdot a_{1} \cdot \ldots \cdot a_{i-1} \cdot b_{i} \cdot a_{i+1} \cdot a_{i+2} \cdot \ldots \cdot a_{m-1}$

where $a_i = c[u_i]$ and $b_i = cn[u_i] \cdot [ dt[v] = dn[v] + 1 + dn[u_i] - dt[u_i] ]$. Let's write $m$ products of this sum in $m$ subsequent rows, forming a $m \times m$ matrix. The following image shows it for $m=5$:

We can calculate this sum by evaluating sums in subsequent submatrices of size $i \times i$ as shown on the image. The value $S_i$ will denote sum of submatrix $i \times i$ and helper value $A_i$ will denote partial product $a_0 \cdot a_1 \cdot \ldots \cdot a_i$. We start with $S_0 = 0$ and $A_0 = 1$, and use the formulas:

$S_i = S_{i-1} \cdot a_i + A_{i-1} \cdot b_i$

$A_i = A_{i-1} \cdot a_i$

The answer is $cn[v] = S_m$. We can also observe that $ct[v] = A_m$. The code following this method is much simpler than the previous one, and what is most important, it does use only constant additional memory:

REP(i, n) { const int v = n-1 - i; cn[v] = 1; ct[v] = 0; for (int it = begin[v]; it < begin[v+1]; ++it) { const int u = it; const int cu = ct[u] + cn[u] * (dn[u] == dt[u]); ct[v] = ct[v] * cu + cn[v] * cn[u] * (dt[v] == dn[v] + 1 + dn[u] - dt[u]); cn[v] *= cu; } }

### Compressing memory usage

Now let's take a closer look at computations for finding maximum size. We showed that $dt[v] \geq dn[v]$, that is maximum-size matching which uses vertex $v$ is no smaller that maximum-size matching which does not use this vertex. But how much bigger it can be? Let's take a matching which uses vertex $v$ and remove the edge matching $v$. Then we get matching one edge smaller which does not use $v$, therefore $dn[v] \geq dt[v] - 1$. Thus these two numbers can differ only by $1$, so let's make a notation:

$dt[v] = dn[v] + z[v] \quad$ where $\quad z[v] \in \{ 0, 1 \}$

This way we no longer have to use $dt[v]$, we just use $dn[v]$ and $z[v]$. Let's rewrite recursions using this new notation. First of all we can simplify Boolean expressions used in the formulas:

$[dn[v] = dt[v]] = [z[v] = 0] = 1 - z[v]$

$[dt[v] = dn[v] + 1 + dn[u_i] - dt[u_i]] = [z[v] = 1-z[u_i]] = z[v] \ \textrm{xor}\ z[u_i]$

Then we can rewrite all formulas:

$dn[v] = \sum_i (dn[u_i] + z[u_i])$

$z[v] = \max_i (1 - z[u_i])$

$c[v] = ct[v] + cn[v] \cdot (1 - z[v])$

$cn[v] = \prod_i c[u_i]$

$ct[v] = \sum_i (cn[v] / c[u_i] \cdot cn[u_i]) \cdot (z[v] \ \textrm{xor}\ z[u_i])$

We have two observations here. First of all, we replaced array dt with array z. It looks like we didn't gain much here, but note that array dt was int array (it used $n$ ints), and z is bit array (it needs only $n$ bits). Bit array uses less memory, since it can be packed. If int has $B$ bits, it uses only $\lceil n/B \rceil$ ints.

But actually we can pack it so it won't use additional memory at all. Recall that we assumed that int variable can store number $2n$. And variable $dn[v]$ stores numbers no larger than $\frac{n}2$. Therefore we can use unused most significant bit in $dn[v]$ to store bit $z[v]$. Thus both arrays to calculate size of maximum-size matching will use only $n$ ints of memory. This reduces memory consumption of DP arrays to $3n$ ints.

What about arrays cn and ct for calculating numbers of maximum-size matchings? Of course, we need them both. But interesting thing is that for calculating them we don't need array dn at all, only bit array z. Thus memory used by dn after we computed first step can be reused (for instance for storing one of cn, ct). But then again, we need to store array z somewhere else. We cannot pack it with cn or ct, because these arrays stores numbers modulo $M$, which possibly uses all of bits in their cells. But don't forget we have one more array we are using: array begin in which we store the tree. It stores numbers up to $n-1$, then each cell of this array has an unused bit. Therefore we can pack array z there.

To recap: first we calculate array dn and bit array z, the latter is packed together with array begin. Next, we calculate cn and ct, using bit array z stored in begin and reusing memory from no longer used array dn. Therefore the total memory consumption from DP arrays decreased to only $2n$ ints.

The following C++ code uses helper macros to quickly get and set bits in array begin.

int* cn = array + N; int* ct = array + 2*N; const int MSB = 19; /* Number of most significant bit in int */ #define BEGIN(i) (begin[i] & ~(1 << MSB)) #define Z(i) (begin[i] >> MSB) #define SETZ(i, val) (begin[i] = BEGIN(i) | (val << MSB)) void iterative_dp_3() { REP(i, n) { const int v = n-1 - i; dn[v] = 0; int zv = 0; for (int it = BEGIN(v); it < BEGIN(v+1); ++it) { const int u = it; const int zu = Z(u); dn[v] += dn[u] + zu; zv |= 1 - zu; } SETZ(v, zv); } REP(i, n) { const int v = n-1 - i; const int zv = Z(v); cn[v] = 1; ct[v] = 0; for (int it = BEGIN(v); it < BEGIN(v+1); ++it) { const int u = it; const int zu = Z(u); const int cu = ct[u] + cn[u] * (1 - zu); ct[v] = ct[v] * cu + cn[v] * cn[u] * (zv ^ zu); cn[v] *= cu; } } }

The cost of the first phase is $(1+4)n$ ints, but we have managed to squeeze the memory used by the second phase to only $2n$ ints. Once again, the memory bottleneck of the algorithm is the first phase, so let's see if we can reduce it, to reduce the total consumption of memory.

So we know that we only need $n$ ints of array to store the tree, and be able to traverse it in order to perform DP computations. In this light, additional $4n$ ints needed to create the array is way too much. Let's take a completely different approach to decrease it.

### Parent representation

The problem is that the representation of a tree as an edge list is not very convenient. It hides the structure of the tree, and if we want to do any traversal over the tree, we must convert it to some other representation. And since it is usually the first thing we do after reading such a tree, in some programming problems that deal with trees, other, more convenient representations are used in the input.

One of such representation is a list of parents. In fact, it comes in two flavors, which we call here strict and relaxed. For the strict variant, we number each vertex with a number from $0$ to $n-1$. Next, we list $n-1$ edges, but the $i$-th edge (one-based) must connect vertex $i$ to some other vertex $p[i]$ of smaller number ($p[i] < i$). That means that by considering edges one by one, we add new vertices to one connected component. Of course, the obvious advantage of this representation is that it only uses $n$ ints to store the tree.

But that representation has another important property: for every vertex $v$ except $0$ there is some edge incident to the vertex which leads to vertex $p[v]$ of a smaller number. Therefore, starting from any vertex $v$ and using such edges, we eventually end up in vertex $0$. That shows that if we root the tree in vertex $0$, then for each non-root vertex $v$ we have that vertex $p[v]$ is the parent of $v$. And also that the number of every child is greater that the number of its parent.

For the relaxed variant, we also number vertices from $0$ to $n-1$, but now we input $n$ numbers $p[i]$ for $0\leq i < n$. One number $i$ is special and we denote it by $p[i]=-1$, and for all other numbers we assume that we have an edge between vertex $i$ and $p[i]$.

Let's denote by $v_\star$ the special vertex for which $p[v_\star] = -1$. If we do the same trick as before: from any vertex $v$ we start moving using edges directed from $i$ to $p[i]$, we finally must arrive at vertex $v_\star$ (since we cannot have any cycle in a tree). That shows that for the relaxed variant, if we root the tree in vertex $v_\star$, then for each non-root vertex $v$ we have that vertex $p[v]$ is the parent of $v$.

So let's imagine that we got parent representation (strict or relaxed) in array p. How can we calculate array begin from it? First is easy to calculate indegree of each vertex (in array deg). Then we just fill array Adj in standard way:

int p[N], deg[N], Adj[N], root; REP(i, n) { if (p[i] != -1) { deg[p[i]]++; } else { root = i; } } REP(i, n-1) { deg[i+1] += deg[i]; } REP(i, n) { if (p[i] != -1) { Adj[deg[p[i]]--] = i; } }

The above code, based on array p, calculates arrays Adj and begin (equal to deg). These two arrays store the full information about the tree in memory using $2n$ ints. So, if we would have array p, we could perform the first phase in $(2+1)n$ ints, and the whole problem in just $4n$ ints. (As a side note: performing DP on arrays obtained from strict variant of parent representation is even easier, since the vertices are already in good order.)

We could also use technique of removing vertex numbers to calculate array begin which fully represent the tree. We no longer need array vis, since Adj does not store parents. So the cost would be $(1+2)n$ ints, which results in only $3n$ ints for the whole problem!

### Obtaining parent representation using xoring

And here it's where magic begins. It turns out that we do not need much memory to calculate parent representation of a tree from its edge list representation, but the idea is quite ingenious. The code is as follows:

int n, deg[N], hash[N], q[N], qe, qb, root; int* p = hash; void load_tree_3() { scanf("%d", &n); REP(i, n-1) { scanf("%d%d", &a, &b); deg[a]++; hash[a] ^= b; deg[b]++; hash[b] ^= a; } REP(i, n) { if (deg[i] == 1) { q[qe++] = i; } } REP(i, n-1) { const int v = q[qb++]; const int p = hash[v]; hash[p] ^= v; if (--deg[p] == 1) { q[qe++] = p; } } root = q[n-1]; p[root] = -1; }

First we just iterate over all edges without storing them and for each vertex $v$ we calculate its degree $deg[v]$ and also $hash[v]$ which stands for bitwise xor of numbers of all vertices adjacent to $v$.

Next we will build the tree from the leaves up to some root. Observe that for any node $v$ of degree $1$, we know that it has exactly one adjacent node, so we know that the number of this adjacent node is $p = hash[v]$. We therefore assume that the parent of vertex $v$ is $p$, and then we remove vertex $v$ from the tree. The removal boils down to decreasing degree of vertex $p$ and un-xoring $v$ from $hash[p]$ which results in a smaller tree which we attack recursively.

Thus we maintain a queue q of leaves of the current tree. At first we put there all vertices with degree $1$. Then we iteratively remove vertex $v$ from the queue, assign its parent $p$, and update $deg[p]$ and $hash[p]$. Anytime degree of such $p$ decreases to $1$, we can push it on the queue.

After removing $n-1$ vertices, we end up with the last vertex on the queue, which becomes the root of the tree, and any other vertex has correctly calculated parent $p[v] = hash[v]$.

We used $3n$ ints for arrays deg, hash and q, but only array p (equal to hash) is needed at the end. Using the code before, we calculate begin, so it results in the first phase of cost $(1+2)n$ ints. Therefore the whole problem can be solved in $3n$ ints; slightly more than one-fifth of original.

### First-child-next-sibling representation

It turns out that we can easily improve the code to calculate array p. Note that use queue q to store vertices of degree $1$, so we know which of them to process later. But is it really necessary? Instead of putting them into queue in the first loop, we could just process them right away. Moreover, if during processing some vertex, its parent became a vertex of degree $1$ we can also process it immediately (which could result in another such parent). Following code does not use queue at all:

REP(i, n) { if (deg[i] == 1) { const int v = i; while (deg[v] == 1) { const int p = hash[v]; hash[p] ^= v; --deg[p]; deg[v] = -1; root = p; v = p; } } } p[root] = -1;

Every removed $v$ vertex is marked by putting $deg[v] = -1$. Last considered vertex will become the parent.

By removing array q we reduced the memory needed to calculate array p to only $(1+1)n$ ints. So maybe we could also reduce memory needed for calculating array begin from array p?

To do this we introduce one more representation of a tree. It is called first-child-next-sibling and for each vertex $v$ we store two numbers: number of its first child $chi[v]$ (equal to $-1$ if vertex has no children) and number of its next sibling $sib[v]$ (number of a child after this vertex in its parent child list; or $-1$ if its last vertex on this list). It's fairly easy to calculate this representation from array of parents:

int chi[N], sib[N]; REP(i, n) { chi[i] = sib[i] = -1; } REP(i, n) if (p[i] != -1) { const int par = p[i]; sib[i] = chi[par]; chi[par] = i; }

Each time we consider new vertex $v$, we assign it as the first child of its parent $p[v]$, and if any vertex was this child before, it will be assigned as next sibling of $v$. Of course, we want to store all computations in $2n$ ints, but this could be done by observing that we can reuse memory between arrays p and sib, since after setting $sib[i]$ we no longer need access to $p[i]$. Thus the first beginning of the above code could look like this:

int chi[N]; int* sib = p; REP(i, n) { chi[i] = -1; }

The representation using chi and sib can be easily used to perform BFS traversal. We start by putting root in the queue q, and every time we visit vertex $v$, we can iterate over its children by starting from $w = chi[v]$ and then performing $w = sib[w]$ until we hit $-1$. Therefore for each visited vertex we can also calculate its outdegree. The trick is to store this number in memory shared by queue q. Finally, because these vertices are in BFS order, we get for free removal of their numbers:

int q[N], qe, qb; q[qe++] = root; while (qe != qb) { const int v = q[qb]; int w = chi[v], d = 0; while (w != -1) { q[qe++] = w; w = sib[w]; ++d; } q[qb++] = d; /* Store degree of v */ } REP(i, n) { const int v = n-1 - i; q[i+1] = q[i]; } q[0] = 1; REP(i, n) { q[i+1] += q[i]; }

The last loop performs calculation of prefix sums in place, starting from $1$ (thus we first need to move array one position to the right). At the end we use only array q as array begin. But we used $3n$ ints in total (for arrays chi, sib and q), so it does not look as an improvement.

### Even more compression with first-child-next-sibling representation

The trick is to squeeze queue q into arrays chi and sib. Since children of each vertex are put sequentially into the queue, array sib already contains these parts of the queue. We only have to concatenate them together, using last vertices in each children list (they have sib equal to $-1$):

int v, ve; int* ndeg = chi; v = ve = root; while (v != -1) { int w = chi[v], d = 0; sib[ve] = w; while (w != -1) { ve = w; w = sib[w]; ++d; } ndeg[v] = d; v = sib[v]; }

During the whole loop, the variable $v$ will iterate over all vertices of the tree, in the BFS order. Since it uses array sib for this iteration, for every vertex $v$ which is the last child on its parent's list we must set $sib[v]$ to the next vertex in this order. Therefore we will maintain variable $ve$ which stores the number of vertex which is directly before $chi[v]$ in the BFS order (or if $v$ has no children, directly before position in which its first children would appear if it has one).

For subsequent vertices $v$ we proceed as follows: if $v$ has children, we put its first child as the next vertex after $ve$. Next, we iterate over all children of $v$, counting them, and updating $ve$ as the number of the last child. Finally, we store outdegree of $v$ in array ndeg, shared with chi, since we won't use $chi[v]$ anymore.

At the end we have array sib which serves as the queue and array ndeg (shared which chi) which stores degrees of nodes (but in original order). The only thing left is to sort array ndeg according to the order stored in array sib:

int pos = root; REP(i, n) { const int nxt = sib[pos]; sib[pos] = i; pos = nxt; } REP(i, n) if (sib[i] != i) { swap(ndeg[i], ndeg[sib[i]]); swap(sib[i], sib[sib[i]]); --i; } int sum = 1; REP(i, n) { swap(sum, ndeg[i]); sum += ndeg[i]; } ndeg[n] = sum;

Note that the order in array sib is given implicitly, as a linked list: the first element is root, then sib[root], next sib[sib[root]] etc. The first loop iterates over this list and for every element $v$ stores in $sib[v]$ the value $i$ which denotes that element $v$ is the $i$-th element in the list.

The second loop reorders array ndeg using order stored in array sib. We iterate over all elements $i$ and for each element which is out of place (i.e. $sib[i] \neq i$) we move this element to its correct position (that is $sib[i]$) and at the same time we move the element which previously was in this position to position $i$. Thus in each iteration one more element is located correctly.

Finally, the last loop performs calculation of prefix sums, starting from $1$, but it does it a little differently than the implementation in the previous section, using only one loop instead of two.

The above clever code perform the first phase using only $(1+1)n$ ints of memory! This is really an achievement, because it allows us to read a tree in list edge representation to a form suitable to perform DP traversal in $(1+1)n$ ints. So for a problem in which we have one DP array of size $n$ it would result in an algorithm using only $2n$ ints in total. In general for a problem with $k$ DP arrays we get $(1+\max(1,k))n$ ints. However, in our problem DP arrays are of size $2n$, so we get $3n$ algorithm, and we have that before.

## Even more improvements in DP calculation

It looks like we really squeezed the memory in this problem. We store the whole tree in one array of $n$ ints. The other two arrays are used for DP calculations. In fact for calculating the size of matching we use only one additional array dn. However, for calculating the number of matchings we need two arrays: both values cn and ct are numbers resulted from rather complicated computations modulo $M$, so it is very unlikely that they have some general properties to be discovered and used in such a way that would result in removing one of them. So it looks like we hit the limit. Or is it?

### Branching and non-branching vertices

But let's don't give up yet. We already did some magic with xoring, so why not try to do something impossible?

If we cannot remove one of DP arrays, maybe we can make them smaller? Do we really have to store the data for all vertices? For instance, we really don't have to do it for leaves. DP values for them are constants which do not depend on other vertices, so we can easily recreate them when needed. When parent vertex is calculating DP it can check whether its child is a leaf, and then do not look into DP table, but just use appropriate constants.

That is an idea that could save us some memory on trees with many leaves. Unfortunately, not all trees are like that: we could have a tree which is a long path that has only one leaf, and then this optimization would give us nothing. But note that this tree is also special and easy to calculate DP on, because it consists of this long path of vertices of degree $1$. The DP values for the top-most vertex of this path could also be calculated in constant memory, as long as we know the length of the path, since DP in each vertex depends only on DP value in one vertex below (we can think of it as a variant of tail optimization). This is true in general case: in every tree we can treat each path of vertices of degree $1$ specially, and we do not need to store DP values for internal vertices of these paths.

So we only need to store DP values for branching vertices, namely those which have at least two children. And in any tree there are at most $\frac{n}{2}$ branching vertices! It follows from two simple facts: sum of branching vertices and leaves is bounded by $n$, and there is more leaves than branching vertices.

Therefore we only need to store $\frac{n}{2}$ values in every DP array. There is one problem though: branching vertices do not necessarily form a contiguous part of arrays, so we need some renumbering mechanism if we want to save memory. To achieve this, we introduce an array $pos$, where in $pos[v]$ we store the position of branching vertex $v$ in the compressed DP array, i.e. $pos[v]$ is the number of branching vertices of smaller numbers than $v$:

int pos[N], last = 0; REP(v, n) { if (BEGIN(v+1) - BEGIN(v) >= 2) { pos[v] = last++; } }

Since the values stored so far in arrays cn and ct will have to be calculated on-the-fly for non-branching vertices, it will be handy to define a structure containing all DP values for a single vertex:

struct dp_t { int cn; int ct; }; dp_t dp[N/2];

The function which returns the constant values for a leaf is very simple:

dp_t leaf() { return dp_t{ 1, 0 }; }

Recall that DP calculation for a single vertex $v$ which children $u_0, \ldots, u_{m-1}$ involve initiating values cn and ct, and iterating over subsequent vertices $u_i$. After the $i$-th iteration the current values cn and ct contain DP values for a vertex $v$, assuming it has only children $u_0, \ldots, u_i$. Therefore we could write a function join(a, b, zv, zu) in which argument a denotes DP values of a tree consisting of vertex $v$ and children $u_0, \ldots, u_{i-1}$, argument b denotes DP values for child $u_i$ and the function returns DP values for a tree consisting of vertex $v$ and children $u_0, \ldots, u_i$. Since DP values depend on values z stored in vertices $v$ and $u_i$, we will also provide them as arguments:

dp_t join(const dp_t& a, const dp_t& b, int zv, int zu) { const int cu = b.ct + b.cn * (1 - zu); const int cn = a.cn * cu; const int ct = a.ct * cu + a.cn * b.cn * (zv ^ zu); return dp_t{ cn, ct }; }

We are ready to create a helper function which allows to retrieve DP values for vertices we already visited. In other words, if $v$ is a branching vertex, we must query an appropriate cell in the compressed DP array, and otherwise, we must recalculate DP values on-the-fly. First of all, if $v$ is a vertex of degree $1$, the function calculates the length of the path to the first vertex $w$ of other degree. Then, if $w$ is a leaf it uses constants, and if $w$ is a branching vertex it queries DP arrays. Finally, it makes DP calculation upwards the path of vertices of degree $1$:

dp_t calc(int v) { int length = 0; while (BEGIN(v+1) - BEGIN(v) == 1) { length++; v = BEGIN(v); } dp_t t; int z = 0; if (BEGIN(v+1) - BEGIN(v) == 0) { t = leaf(); } else { t = dp[pos[v]]; /* Querying value in dp array */ z = Z(v); } while (length--) { t = join(leaf(), t, 1-z, z); z = 1-z; } return t; }

The only non-clear part of this function is how we handle retrieval of values z when calculating DP on the path of vertices of degree $1$. The problem is that we store values z packed in array begin. When in the first loop we go downwards the path, calculating its length, we obtain numbers of subsequent vertices $v$ on this path. We could obtain values z for these vertices using Z(v). However, in the last loop we go upwards the path, so we would need the sequence of these numbers, but it reverse order. The problem is that we cannot afford to store this sequence, so we do not know numbers of vertices when we go upwards the path.

Fortunately we can calculate values of z in a path of degree $1$ directly from the definition (recursive formula). In fact, when vertex $v$ has exactly one child $u$, then Z(v) = 1 - Z(u).

Finally, we can present the main code to calculating values cn and ct for all vertices:

REP(i, n) { const int v = n-1 - i; if (BEGIN(v+1) - BEGIN(v) >= 2) { dp_t t = leaf(); for (int i = BEGIN(v); i < BEGIN(v+1); ++i) { t = join(t, calc(i), Z(v), Z(i)); } dp[pos[v]] = t; /* Updating value in dp array */ } }

Since the on-the-fly calculations in function calc(i) depend on the length of the path starting in vertex $i$, so the time complexity is a little bit suspicious. Fortunately, we call this function only on vertices $i$ which have branching parent, all such paths traversed by the algorithm are disjoint, and the time complexity of the algorithm is still $O(n)$.

The above algorithm uses additional array pos of size $n$ ints, but thanks to that the DP arrays are half as big as before. Therefore for $k$ DP arrays it uses memory of $(2+k/2)n$ ints. This is definitely improvement for big values of $k$, but in our problem it still results in algorithm which uses $3n$ ints. We really need something better.

### Destructively traversing the tree

One could argue that we do not have to store array pos, since each of its elements can be computed in constant memory from array begin. Unfortunately, this needs $O(n)$ time, and since we query array pos in arbitrary order (when iterating other subsequent children which have paths underneath, we in fact query vertices on different heights) this would lead to quadratic time, which is unacceptable.

So if we really need to store pos, but we don't want to spare additional memory, we must once again reuse some already allocated memory. But apart from array dp storing DP values, we only have array begin which is essential for tree traversal. Or is it?

Observe, that we iterate over vertices in reversed BFS order, and after processing of branching vertex $v$ we will not longer use values of $begin[u]$ for most vertices $u$ is the subtree of $v$. To be more precise: we will use $begin[v]$ and $begin[v+1]$ when later querying the number of children of $v$. Also if $u_0, u_1, \ldots, u_{m-1}$ are children of $v$, then we could use $begin[u_0]$ when querying the number of children of $u_0-1$ (especially if $v=u_0-1$). But we won't be querying for number of children of $u_0$ and $u_1$ (or iterating over them), thus we won't be needing value $begin[u_1]$ of the second child of $v$ (note that $v$ has the second child, since it is branching). We also won't be using value z stored in this cell. Thus we can reuse this field to store $pos[v]$.

That requires only slight changes to the previous algorithm. First, we do not need pos array anymore (and its initialization code). Next, the line updating value in dp array should be replaced with:

dp[ begin[BEGIN(v)+1] = last++ ] = t;

And querying this array in function calc should be replaced with:

t = dp[ begin[BEGIN(v)+1] ];

This is quite unbelievable, but this algorithm runs one DP traversal for $k$ DP arrays in memory of only $(1 + \max(1, k/2))n$ ints. Unfortunately, as a nasty side-effect it destroys the traversed tree. Therefore it is not practical, if we want to make more than one pass over the tree.

In our problem we need two passes, but we already discussed that the first pass uses only one DP array, thus it can be done using non-destructive methods in memory $(1 + 1)n$ ints. In the second pass we use the above trick, destructively calculating number of matchings in the same memory.

And this is our final algorithm. It uses memory of only $2n$ ints to input the tree and perform non-trivial DP calculations on it. Compared with at least $14n$ ints needed by the standard approach, it's an improvement of one-seventh of the original. I told you that it will be a lot.

## Conclusions

I learned a lot when writing this article, and I hope that the readers will also find it useful. Because not only the problem of dynamic programming on trees using as small memory as possible gave us an excuse to talk about important implementation details of memory management (in context of vectors, malloc and recurrence), various representations of trees in memory and ways to compress DP arrays. It was also a perfect quest for ingenious ideas in computing, once called by Michael Abrash as these astonishing “right-brain optimizations”.


text:
# Graph and/or Chart

Any advice on how to draw this generic graph? I said "generic" because is not based on any data, so apparently there are no references nor coordinates.

This is as far as I can go:

\documentclass{standalone}
\usepackage{tikz}
\usetikzlibrary{patterns,hobby}
\usepackage{pgfplots}
\pgfplotsset{compat=1.6}
\begin{document}
\begin{tikzpicture}

\begin{axis}[
xmin=-0,xmax=7,
xlabel={z},
ymin=0,ymax=4.5,
xtick={2,4.5,6},
xticklabels={$t$,$t+dt$,$n$},
ytick={3.5},
yticklabels={$V(x)$},
xlabel={},
ylabel={},
axis lines=middle]
\draw [color=black,fill=white,thick,solid] (axis cs:0,0) rectangle (axis cs:6,3.5);
\draw [color=black,fill=white,thick,solid] (axis cs:0,0) rectangle (axis cs:2,3.5);
%
\node  at (axis cs:2.5,0)    [anchor=south west] {$$}; \node at (axis cs:4,0) [anchor=south west] {$$};
\node  at (axis cs:2.8,2.2)  [anchor=north]      {$$}; \node at (axis cs:4.2,4) [anchor=north] {$$};
\node  at (axis cs:0.25,2.5) [anchor=north]      {$$}; \node at (axis cs:0.25,4) [anchor=north] {$$};
\node at (axis cs:0,0)     [anchor=south west]  {};
%
\end{axis}
\end{tikzpicture}
\end{document}

• It is very straightforward, you could start by defining all relevant coordinates on the drawing and then draw some lines and a few arrows. – daleif May 3 '16 at 16:44
• here's starting point perhaps: tex.stackexchange.com/questions/160237/… – Thruston May 3 '16 at 17:20
• compat=1.6, really? The latest version of pgfplots is 1.13. – Torbjørn T. May 3 '16 at 19:06

An alternative, pure TikZ solution:

\documentclass[tikz,border=3mm,preview]{standalone}
\usetikzlibrary{arrows.meta,positioning,quotes}

\begin{document}
\begin{tikzpicture}[
>={Triangle[]}
]
% coordinate
\draw[->] (-0.1,0) node[below left] {0}
-- (9,0);
\draw[->] (0,-0.1) -- (0,6);
% horizontal line
\draw   (-0.1,4) node[left] {$V(x,0)$} -- + (9,0);
% vertical lines
\draw   (2,4) node[above left] {$V(x,t)$}
node[below left] {$P(x,t)\mathrm{d}t$}
-- + (0,-4.1)
node[below] {$t$};
\draw   (5,4) node[above right] {$V(x,t+\mathrm{d}t)$}
-- + (0,-4.1)
node[below] {$t+\mathrm{d}t)$};
\draw   (8,4) node[above] {$V(x,n)$}
-- + (0,-4.1)
node[below] {$n$};
% vectors
\path[draw=red, fill=red, ultra thick, ->]
(2,4) edge["$\displaystyle 1-\sum_{j=1}^{k}\mu_{x+t}^{(j)}\mathrm{d}t$"]   + (3, 0)
(2,4) to [pos=0.7,sloped,"$\displaystyle \mu_{x+t}^{(j)}\mathrm{d}t$" ']                 + (3,-2);
\end{tikzpicture}
\end{document}

• Great. It's the way I need. The detail of the sloped formula is superb. Thanks a lot!! – José May 4 '16 at 6:38

Another way with TikZ. I like to separate the labels from the drawings.

\documentclass[border=5mm]{standalone}
\usepackage{tikz}
\usepackage{amsmath}
\begin{document}
\begin{tikzpicture}[axis/.style={thick,-stealth},
vector/.style={ultra thick,-latex}
]
% drawing
\draw [axis] (0,0) -- (13,0);
\draw [axis] (0,0) -- (0,6);
\draw[thick] (0,4)  -- (13,4);
\foreach \i in {1,2,3}{%
\draw[thick] (4*\i,0) -- (4*\i,4);
}
\draw [vector] (4,4) --  (8,4);
\draw [vector] (4,4) --  (8,4/3) coordinate[midway](mi) coordinate(e);
% the labels
\foreach \i/\l/\a in {  0/{V(x,0)}/left,
1/{V(x,t)}/left,
2/{V(x,t+dt)}/right,
3/{V(x,n)}/left}{%
\node[above \a] at (4*\i,4) {$\l$};
}
\foreach \i/\l in { 0/0,
1/t,
2/t+dt,
3/n}{%
\node[below] at ((4*\i,0) {$\l$};)
}
\node[above=8pt] at (6,4) {%
$\displaystyle 1-\sum_{j=1}^{k}\mu_{x+t}^{(j)}\,dt$};
\node[below left] at (mi) {$\mu_{x+t}^{(j)}\,dt$};
\node[right] at (e) {$S_{x+t}^{(j)}$};
\node[below left] at (4,4) {$P(x,t)\,dt$};
\end{tikzpicture}
\end{document}

This is the kind of thing where I wouldn't use pgfplots at all.

• If you want to change the width/height of the diagram, change x=8cm,y=4cm to your liking. The axis lines are drawn from (0,0) to (0,1)/(1,0).

• If you want to raise or lower the horizontal line, modify the value in \pgfmathsetmacro\Y{0.7} to some value between 0 and 1.

• If you want to move the three vertical lines, modify the values for \Xa, \Xb and \Xc. Again, use values between 0 and 1.

\documentclass[border=5mm]{standalone}
\usepackage{tikz}
\usepackage{amsmath}
\begin{document}
\begin{tikzpicture}[
axis/.style={thick,-stealth},
vector/.style={ultra thick,-latex},
x=8cm,y=4cm,
every node/.style={font=\small}
]
\draw [axis] (0,0) node[below left] {$0$} -- (1,0);
\draw [axis] (0,0) -- (0,1);

\pgfmathsetmacro\Y{0.7}
\pgfmathsetmacro\Xa{0.3}
\pgfmathsetmacro\Xb{0.65}
\pgfmathsetmacro\Xc{0.9}

\draw (0,\Y) node[left] {$V(x,0)$} -- (1,\Y);

\foreach \x/\txt/\anchor in {\Xa/t/330,\Xb/t+dt/210,\Xc/n/230}
\draw (\x,\Y) node[above,anchor=\anchor]{$V(x,\txt)$} -- (\x,0) node[below] {$\txt$};

\draw [vector] (\Xa,\Y)
-- node[above]{$\displaystyle 1-\sum_{j=1}^{k}\mu_{x+t}^{(j)}\,dt$}
(\Xb,\Y);
\draw [vector] (\Xa,\Y) node[below left] {$P(x,t)\,dt$}
-- node[below left] {$\mu_{x+t}^{(j)}\,dt$}
(\Xb,\Y/3) node[right] {$S_{x+t}^{(j)}$};

\end{tikzpicture}
\end{document}

• It worked perfectly! Interesting the point to change the width and height of the diagram. Thanks!!! – José May 4 '16 at 6:41

A PSTricks solution:

\documentclass{article}

\usepackage{mathtools}

\newcommand*\diff[1]{\mathop{}\!\mathrm{d}#1}
\def\arrow[#1](#2)(#3)#4{%
\psline[linewidth = 2.5\pslinewidth]{->}(#2)(#3)
\pcline[linestyle = none, offset = #1](#2)(#3)
\ncput{$\displaystyle #4$}}

\begin{document}

\begin{pspicture}(-1.23,-0.4)(10,6.5)
\pnodes(0,0){A}(2.5,0){B}(7,0){C}(9,0){D}(7,2){E}(0,5){F}(2.5,5){G}(7,5){H}(9,5){I}(10,5){J}
\psline{<->}(0,6.5)(A)(10,0)
\uput[225](A){$0$}
\psline(F)(J)
\uput[180](F){$V(x,0)$}
\psline(B)(G)
\uput[270](B){$t$}
\psline(C)(H)
\uput[270](C){$t+\diff{t}$}
\psline(D)(I)
\uput[270](D){$n$}
\arrow[19pt](G)(H){1-\sum_{j = 1}^{k}\mu_{x+t}^{(j)}\diff{t}}
\arrow[-15pt](G)(E){\mu_{x+t}^{(j)}\diff{t}}
\uput[90](G){$V(x,t)$}
\uput[225](G){$P(x,t)\diff{t}$}
\uput[0](E){$S_{x+t}^{(j)}$}
\uput[90](H){$V(x,t+\diff{t})$}
\uput[90](I){$V(x,n)$}
\end{pspicture}

\end{document}

In case you want the formulae to be tilted to follow the directions of the arrows instead of always being horizontal, you can add the option nrot = :U to \ncput:

\documentclass{article}

\usepackage{mathtools}

\newcommand*\diff[1]{\mathop{}\!\mathrm{d}#1}
\def\arrow[#1](#2)(#3)#4{%
\psline[linewidth = 2.5\pslinewidth]{->}(#2)(#3)
\pcline[linestyle = none, offset = #1](#2)(#3)
\ncput[nrot = :U]{$\displaystyle #4$}}

\begin{document}

\begin{pspicture}(-1.23,-0.4)(10,6.5)
\pnodes(0,0){A}(2.5,0){B}(7,0){C}(9,0){D}(7,2){E}(0,5){F}(2.5,5){G}(7,5){H}(9,5){I}(10,5){J}
\psline{<->}(0,6.5)(A)(10,0)
\uput[225](A){$0$}
\psline(F)(J)
\uput[180](F){$V(x,0)$}
\psline(B)(G)
\uput[270](B){$t$}
\psline(C)(H)
\uput[270](C){$t+\diff{t}$}
\psline(D)(I)
\uput[270](D){$n$}
\arrow[19pt](G)(H){1-\sum_{j = 1}^{k}\mu_{x+t}^{(j)}\diff{t}}
\arrow[-12pt](G)(E){\mu_{x+t}^{(j)}\diff{t}}
\uput[90](G){$V(x,t)$}
\uput[225](G){$P(x,t)\diff{t}$}
\uput[0](E){$S_{x+t}^{(j)}$}
\uput[90](H){$V(x,t+\diff{t})$}
\uput[90](I){$V(x,n)$}
\end{pspicture}

\end{document}

• Sometimes I got a problem with the PStrick package when I run/compile together with .cls or .sty. As I am writing my PhD dissertation I have to run several files and not always works as I expected. I will try this time with this code. Thank you very much. – José May 4 '16 at 6:46
• Sorry but how can I do that? :( – José May 5 '16 at 15:14
• – Svend Tveskæg May 6 '16 at 4:46

format: plain


text:
# [web] PHP issues

This topic is 2601 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello.

Having a rather odd issue here. At the moment im trying to relearn PHP as i haven't done it in a few years. And at the moment i'm creating a simple login form though i have issues with it all. After filling in the login information I end up at my sq-connect.php file but nothing is happening. All i get is a white screen. From my experience that mean that display_errors in php.ini isnt activated so it doesnt show whats wrong. That i have already checked. And i know you could insert ini_set('display_errors', 1) to show whats wrong. I have tried but still nothing.
Code is as follows bellow

Index.php
 <form name="form" method="post" action="sq-connect.php"> Login:
 <input type="text" name="LoginUser" id="LoginUser" />
 Password:
 <input type="password" name="PasswordUser" id="PasswordUser" />
 <input type="submit" name="Send" id="Send" value="Faceroll" /> </form>

sq-connect.php
 <? ini_set('display_errors', 1); ini_set('log_errors', 1); ini_set('error_log', dirname(__FILE__) . '/error_log.txt'); error_reporting(E_ALL); ob_start(); // Define connection Information $host="127.0.0.1";$username="*****"; $password="*****";$db_name="****"; $tbl_name="SQAccount"; // Start connection to MYSQL Server mysql_connect("$host","$username","$password")or die("Server doesnt like what you do."); mysql_select_db("$db_name")or die("No ice cream"); // Get info from LoginForm$LoginUser=$_POST['LoginUser'];$PasswordUser=$_POST['PasswordUser'];$Encrypted_password=md5($PasswordUser); // Check if used correct information$sql="SELECT * FROM $tbl_name WHERE UserName='$LoginUser' and PassWord='$Encrypted_password'";$result=mysql_query($sql);$count=mysql_num_rows($result); if($count==1) { session_register("LoginUser"); session_register("PasswordUser"); header("location:opendoor.php"); } else{ echo "Dont lie to me" } ob_end_flush(); ?>

Anyone got a clue what im doing wrong here?

##### Share on other sites
Maybe I'm just being stupid, but don't you need to start with "<?php" instead of just "<?"?

##### Share on other sites

Maybe I'm just being stupid, but don't you need to start with "<?php" instead of just "<?"?

I've used the <?php before but it didnt make any diff. Searched a little on google and found you could do <? with PHP5.

##### Share on other sites
The only 'major' problem I see here is that you have a missing semicolon after your echo statement:

else{ echo "Dont lie to me" }

There's a few other problems I can see too, such as your mysql_query might be failing, or that PHP is giving an undefined index error with your $_POST variables, though most servers will just silently drop this type of error. Also the session_register function was deprecated a while ago (PHP 4.3 I think?), and you now register sessions like any other array: $_SESSION['LoginUser'] = true; $_SESSION['PasswordUser'] = true; And lastly, you seem to be missing a session_start() function at the top of your file, which you need to call before using any session related variables or functions. Any of these could be giving you an error. #### Share this post ##### Link to post ##### Share on other sites When you fix your current problem, you should do some research on how to avoid SQL injection. #### Share this post ##### Link to post ##### Share on other sites When you fix your current problem, you should do some research on how to avoid SQL injection. There is already code for it. I just excluded it as i didnt saw it relevant. #### Share this post ##### Link to post ##### Share on other sites When you fix your current problem, you should do some research on how to avoid SQL injection. In addition to this, please use proper code style too It's hard to read your code. Example needed? $username="*****"; $PasswordUser=$_POST['PasswordUser']; $Encrypted_password=md5($PasswordUser);

Either all lower case or all camel case or the first letter capitalized and all others not and so on.

Oh and btw, you said you see nothing (white screen). But what's up with your error file? Was it created? Is something in there?

ini_set('error_log', dirname(__FILE__) . '/error_log.txt');

##### Share on other sites

Nope nothing was created. I have a feeling its some kind of module I'm missing. As I'm running my own CentOS VPS that I setup on server at work (Working in the Webhosting business).

Yea I know. Trying to make it easy to read but haven't coded properly since I was in Highschool. Thats like 6 years ago. But hopefully i'll start to code properly once i start to get things right.

• 16
• 9
• 13
• 41
• 15


text:
# Compact Disinfectant and Sanitizer Spraying/Fogging Machine

• Rs. 4,199.00
Unit price per
• Save Rs. 4,800

• 900 Watt
• Portable & Easy to operate.
• For High Density Smoke, Make solution of 30% glycerol. The remaining 70% is made up with the alcohol disinfectant.
• For Medium Density Smoke, make a solution of 20% glycerol. The remaining 80% is made up with alcohol disinfectant.
• For Low Density Smoke, make a solution of 15% glycerol. the remaining 85% is made up with alcohol disinfectant.


text:
FANDOM

32,041 Pages

Release spiritual energy mighty enough to rend the earth.
—Description, Final Fantasy Tactics.

Shockwave (衝撃波, Shōgekiha?), also known as Shock Wave or Blast Wave, is a recurring enemy ability that inflicts non-elemental damage, and either to one party member or the entire party, and is usually used by bosses.

AppearancesEdit

Final Fantasy VIEdit

VI Shockwave is an enemy ability used first by Dadaluma, and then later in the Advance remake by Kaiser Dragon. It inflicts minor non-elemental damage to one character. It has a Spell Power of 25 with a Hit Rate of 120, and it cost 20 MP for the enemy to use.

Dirge of Cerberus -Final Fantasy VII-Edit

FFVIIDoC Grand Shockwave, which is used by both Weiss Empowered and Azul, and Ground Shockwave, which is used by Rosso, are enemy abilities that deal non-elemental damage which will only connect if Vincent is still on the ground.

Final Fantasy IXEdit

IX Shockwave, used by Soulcage, Nova Dragon, and Silver Dragon, inflicts major non-elemental damage to the party, while Blue Shockwave is an ability used by Necron, cutting a single character's HP down to one.

Final Fantasy XEdit

X Shockwave is an enemy ability used by One-Eye, which inflicts major non-elemental damage to all characters as well as inflicting Blind, Sleep, Slow, Poison, Confuse, and Silence.

Final Fantasy X-2Edit

X-2 Shockwave is a Machinations ability usable by Rikku's special dressphere, Machina Maw. It takes 20 AP to master and 36 MP to cast, and inflicts major, non-elemental physical damage to the enemy's party.

Final Fantasy XIEdit

XI Shockwave is a Great Sword Weapon Skill which deals area of effect damage and inflicts Sleep.

This article or section is a stub about an ability in Final Fantasy XI. You can help the Final Fantasy Wiki by expanding it.

Final Fantasy XIIEdit

XII Shock Wave is used by several enemies in the game, such as gargoyle-type enemies, mantis-type, and Headless. It inflicts physical damage and may cause Knockback.

This article or section is a stub about an ability in Final Fantasy XII. You can help the Final Fantasy Wiki by expanding it.

Final Fantasy XIII-2Edit

XIII-2 Blast Wave is an enemy ability exclusive to Caius Ballad. It manifests as a straight line of purple energy dealing large magical damage, has wounding effects applied to it, and can launch any target that may come in contact with it.

Final Fantasy XIVEdit

This article or section is a stub about an ability in Final Fantasy XIV. You can help the Final Fantasy Wiki by expanding it.

Final Fantasy Tactics A2: Grimoire of the RiftEdit

TA2 The damage formula for Shockwave, as well as all other damaging Martial Arts (except Pummel) is as follows:

$0.5 x Physical Attack x (Physical Attack + PWR)$

The success rate for Shockwave is as follows:

$Physical Attack + PWR$
This article or section is a stub about an ability in Final Fantasy Tactics A2: Grimoire of the Rift. You can help the Final Fantasy Wiki by expanding it.

Final Fantasy Type-0Edit

TYPE0 Shock Wave is a command for the Bahamut-Class Eidolons Bahamut and Neo Bahamut.

This article or section is a stub about Summon magic in Final Fantasy Type-0. You can help the Final Fantasy Wiki by expanding it.

Final Fantasy Crystal Chronicles: My Life as a DarklordEdit

This article or section is a stub about an ability in Final Fantasy Crystal Chronicles: My Life as a Darklord. You can help the Final Fantasy Wiki by expanding it.

Dissidia Final Fantasy Opera OmniaEdit

This article or section is a stub about an ability in Dissidia Final Fantasy Opera Omnia. You can help the Final Fantasy Wiki by expanding it.

Pictlogica Final FantasyEdit

This article or section is a stub about an ability in Pictlogica Final Fantasy. You can help the Final Fantasy Wiki by expanding it.

This article or section is a stub about an ability in Final Fantasy Airborne Brigade. You can help the Final Fantasy Wiki by expanding it.

Final Fantasy All the BravestEdit

This article or section is a stub about an ability in Final Fantasy All the Bravest. You can help the Final Fantasy Wiki by expanding it.

Final Fantasy Record KeeperEdit

This article or section is a stub about an ability in Final Fantasy Record Keeper. You can help the Final Fantasy Wiki by expanding it.

EtymologyEdit

In physics, a shock wave (also spelled shockwave), or shock, is a type of propagating disturbance. When a wave moves faster than the local speed of sound in a fluid it is a shock wave. Like an ordinary wave, a shock wave carries energy, and can propagate through a medium; however it is characterized by an abrupt, nearly discontinuous change in pressure, temperature and density of the medium.


text:
Wilson Machine Tools, Inc., a manufacturer of fabricated metal products, is consideringpurchasing a... 1 answer below »

Wilson Machine Tools, Inc., a manufacturer of fabricated metal products, is consideringpurchasing a high-tech computer-controlled milling machine at a cost of$95,000. The cost of installing the machine, preparing the site, wiring, and rearrangingother equipment is expected to be$15,000. This installation cost will beadded to the cost of the machine to determine the total cost basis for depreciation.Special jigs and tool dies for the particular product will also be required ata cost of $10,000. The milling machine is expected to last 10 years, the jigs anddies only 5 years. Therefore, another set of jigs and dies has to be purchased atthe end of 5 years. The milling machine will have a$10,000 salvage value at theend of its life, and the special jigs and dies are worth only $300 as scrap metal at any time in their lives. The machine is classified as a 7-year MACRS property, and the special jigs and dies are classified as a 3-year MACRS property. With the new milling machine, Wilson expects an additional annual revenue of$80,000 due to increased production. The additional annual production costs are estimated as follows: materials, $9,000; labor,$15,000; energy, $4,500; and miscellaneous O&M costs,$3,000. Wilson’s marginal income tax rate is expected to remain at 35% over the project life of 10 years. All dollar figures represent today’s dollars. The firm’s market interest rate is 18%, and the expected general inflation rate during the project period is estimated at 6%.

(a) Determine the project cash flows in the absence of inflation.

(b) Determine the internal rate of return for the project in (a).

(c) Suppose that Wilson expects price increases during the project period: materialat 4% per year, labor at 5% per year, and energy and other O&M costs at3% per year. To compensate for these increases in prices,Wilson is planningto increase annual revenue at the rate of 7% per year by charging its customersa higher price. No changes in salvage value are expected for the machineor the jigs and dies. Determine the project cash flows in actual dollars.

(d) In (c), determine the real (inflation-free) rate of return of the project.

(e) Determine the economic loss (or gain) in present worth caused by inflation.

Vipul M
Wilson Machine Tools is considering purchasing a high-tech computer-controlled milling machine at a cost of$95,000. The cost of installing the machine is expected to be$15,000. Special jigs and tool dies for the particular product will also be required at a cost of $10,000. The milling machine is expected to last 10 years, the jigs and dies only 5 years. Therefore, another set of jigs and dies has to be purchased atthe end of 5 years. The milling machine will have a$10,000 salvage value at theend of its life, and the special jigs and dies are worth only \$300 as scrap metal at any time in their lives. The machine is classified as a 7-year MACRS property, and the special jigs and dies are classified as a 3-year MACRS property. With the new milling machine, Wilson...

Plagiarism Checker

Submit your documents and get free Plagiarism report

Free Plagiarism Checker

Recent Questions in Macro Economics

Looking for Something Else? Ask a Similar Question


text:
NEET Physics Waves Questions Solved

A standing wave is represented by

$Y=A\mathrm{sin}\left(100t\right)\mathrm{cos}\left(0.01x\right)$

where Y and A are in millimetre, t is in seconds and x is in metre. The velocity of wave is

(1) 104 m/s

(2) 1 m/s

(3) 10–4 m/s

(4) Not derivable from above data

Explanation is a part of a Paid Course. To view Explanation Please buy the course.

Difficulty Level:


text:
# Prediction interval on X with Poisson

What I'm trying to do is predict some biodata based on time. Because the biodata are not normally distributed, I have modeled them with a poisson using a log link function ( E[y] = exp[BX]). What I'm trying to do is estimate the time at which the predicted curve reaches a certain threshold. (i.e., y=1 when x=?). Obtaining a point estimate is fairly straightforward, but I would like to place a confidence interval around that time (e.g., x = 5+-1).

My initial idea was to flip the x and the y and generate prediction intervals as one normally would. However, x is normally distributed while y is poisson, so that's not a good solution. Any other ideas?

• what do you mean by 'the predicted line' ... what line is that? did you fit some kind of model? can you be more specific? – Glen_b Dec 18 '13 at 1:59
• the fitted line. I find the best-fitting line that relates x to y. The fitted line will have the form y=exp(b0 +b1x). Does that help? – dfife Dec 18 '13 at 13:50
• To answer my own question--one option is to bootstrap. – dfife Dec 18 '13 at 13:52
• Hang on -- you're fitting a GLM with log link? I really don't know how a reader is supposed to have known you meant a Poisson GLM with $E(y)=\exp(b_0 +b_1x)$ from "the predicted line". Such a relationship is more usually described as a curve than a line (unless you meant a prediction interval for the linear predictor, $\eta=\log\mu$, but that's a CI not a PI). Could you add the details about your model to your question, please? – Glen_b Dec 18 '13 at 18:38
• When you say that $x$ is normal: the usual assumptions (in regression and GLMs) is that the x-variables are observed without error. If $x$ is, as it sounds, a random variable, then I worry that it might not be the case that x is observed without error (in which case you have all the issues of errors-in-variables). If that's not an issue, then I think you're in the Poisson-regression equivalent of an inverse regression problem. – Glen_b Dec 18 '13 at 23:15


text:
# The Base Jax Class¶

The MathJax.InputJax, MathJax.OutputJax and MathJax.ElementJax classes are all subclasses of the base Jax class in MathJax. This is a private class that implements the methods common to all three other jax classes.

Unlike most MathJax.Object classes, calling the class object creates a subclass of the class, rather than an instance of the class. E.g.,

MathJax.InputJax.MyInputJax = MathJax.InputJax({
id: "MyInputJax",
version: "1.0",
...
});

creates MathJax.InputJax.MyInputJax as a subclass of MathJax.InputJax.

## Class Properties¶

directory

The name of the jax directory (usually "[MathJax]/jax"). Overridden in the subclass to be the specific directory for the class, e.g. "[MathJax]/jax/input".

extensionDir

The name of the extensions directory (usually "[MathJax]/extensions").

## Instance Properties¶

id

The name of the jax.

version

The version number of the jax.

directory

The directory for the jax (e.g., "[MathJax]/jax/input/TeX").

require: null

An array of files to load before the jax.js file calls the MathJax.Ajax.loadComplete() method.

config: {}

An object that contains the default configuration options for the jax. These can be modified by the author by including a configuration subsection for the specific jax in question.

## Methods¶

Process(script)

This is the method that the MathJax.Hub calls when it needs the input or output jax to process the given math <script>. Its default action is to start loading the jax’s jax.js file, and redefine itself to simply return the callback for the load operation (so that further calls to it will cause the processing to wait for the callback). Once the jax.js file has loaded, this method is replaced by the jax’s Translate() method, so that subsequent calls to Process() will perform the appropriate translation.

Parameters: script — reference to the DOM
Translate(script)

This is a stub for a routine that should be defined by the jax’s jax.js file when it is loaded. It should perform the translation action for the specific jax. For an input jax, it should return the ElementJax object that it created. The Translate() method is never called directly by MathJax; during the loadComplete() call, this function is copied to the Process() method, and is called via that name. The default Translate() method throws an error indicating that the Translate() method was not redefined. That way, if the jax.js file fails to load for some reason, you will receive an error trying to process mathematics with this jax.

Parameters: script — reference to the DOM
Register(mimetype)

This method is overridden in the InputJax, OutputJax and ElementJax subclasses to handle the registration of those classes of jax.

Parameters: mimetype — the MIME-type to be associated with the jax null
Config()

Inserts the configuration block for this jax from the author’s configuration specification into the jax’s config property. If the configuration includes an Augment object, that is used to augment the jax (that is, the configuration can override the methods of the object, as well as the data). This is called automatically during the loading of the jax.js file.

Startup()

This is a method that can be overridden in the subclasses to perform initialization at startup time (after the configuration has occurred).


text:
Home OALib Journal OALib PrePrints Submit Ranking News My Lib FAQ About Us Follow Us+
 Title Keywords Abstract Author All
Search Results: 1 - 10 of 100 matches for " "
 Page 1 /100 Display every page 5 10 20 Item
 Physics , 1998, DOI: 10.1103/PhysRevC.60.054606 Abstract: We study the coherent photoproduction of pseudoscalar mesons---particularly of neutral pions---placing special emphasis on the various sources that put into question earlier nonrelativistic-impulse-approximation calculations. These include: final-state interactions, relativistic effects, off-shell ambiguities, and violations to the impulse approximation. We establish that, while distortions play an essential role in the modification of the coherent cross section, the uncertainty in our results due to the various choices of optical-potential models is relatively small (of at most 30%). By far the largest uncertainty emerges from the ambiguity in extending the many on-shell-equivalent representations of the elementary amplitude off the mass shell. Indeed, relativistic impulse-approximation calculations that include the same pionic distortions, the same nuclear-structure model, and two sets of elementary amplitudes that are identical on-shell, lead to variations in the magnitude of the coherent cross section by up to factors of five. Finally, we address qualitatively the assumption of locality implicit in most impulse-approximation treatments, and suggest that the coherent reaction probes---in addition to the nuclear density---the polarization structure of the nucleus.
 Physics , 2015, DOI: 10.1016/j.physletb.2015.11.012 Abstract: We argue that with an increase of the collision energy, elastic photoproduction of $\rho$ mesons on nuclei becomes affected by the significant cross section of photon inelastic diffraction which results in the sizable inelastic nuclear shadowing correction to $\sigma_{\gamma A \to \rho A}$ and by an enhanced contribution of weakly-interacting hadronic configurations in the photon which reduces the effective $\rho$-nucleon cross section. We take these effects into account by combining the vector meson dominance model, upgraded to include the contribution of high-mass fluctuations according to QCD constraints, with the Gribov-Glauber approximation for nuclear shadowing, where the inelastic nuclear shadowing is included by means of cross section fluctuations. The resulting approach allows us to successfully describe the data on elastic $\rho$ photoproduction on nuclei in heavy ion UPCs in the $7 < W_{\gamma p} < 46$ GeV energy range and to predict the value of the cross section of coherent $\rho$ photoproduction in Pb-Pb UPCs at $\sqrt{s_{NN}}=5.02$ TeV in Run 2 at the LHC, $d\sigma_{Pb Pb \to \rho Pb Pb} (y=0)/dy= 560 \pm 25$ mb.
 Physics , 2013, DOI: 10.1140/epja/i2013-13038-3 Abstract: Coherent photoproduction of $\pi^0$-mesons from threshold ($E_{th} \approx$ 136 MeV) throughout the $\Delta$-resonance region and of $\eta$-mesons close to the production threshold ($E_{th} \approx$ 570 MeV for $\eta$) has been measured for $^7$Li nuclei. The experiment was performed using the tagged-photon beam of the Mainz MAMI accelerator with the Crystal Ball and TAPS detectors combined to give an almost 4$\pi$ solid-angle electromagnetic calorimeter. The reactions were identified by a combined invariant-mass and missing-energy analysis. A comparison of the pion data to plane-wave impulse modelling tests the nuclear mass form factor. So far coherent $\eta$-production had been only identified for the lightest nuclear systems ($^2$H and $^3$He). For $^3$He a large enhancement of the cross section above plane-wave approximations had been reported, indicating the formation of a quasi-bound state. The present Li-data for $\eta$-production agree with a plane-wave approximation. Contrary to $^3$He, neither a threshold enhancement of the total cross section nor a deviation of the angular distributions from the expected form-factor dependence were observed.
 Laith Abu-Raddad Physics , 2000, Abstract: The subject of this doctoral study is the pseudoscalar meson photoproduction from nuclei. Two types of processes are investigated in this regard: coherent and quasifree processes. In the case of the coherent process, we study it for the photoproduction of pion and eta mesons. We place special emphasis on the various sources that put into question earlier nonrelativistic-impulse-approximation calculations. These include: final-state interactions, relativistic effects, off-shell ambiguities, and violations to the impulse approximation. By far the largest uncertainty emerges from the ambiguity in extending the many on-shell-equivalent representations of the elementary amplitude off the mass shell. In the case of the quasifree process, we study it for the photoproduction of the kaon meson. We compute the recoil polarization of the lambda-hyperon and the photon asymmetry as well as the differential cross section. By introducing the notion of a bound-nucleon propagator'' we exploit Feynman's trace techniques to develop closed-form, analytic expressions for all photoproduction observables. Our results indicate that polarization observables are sensitive only to the fundamental physics, making them ideal tools for the study of modifications to the elementary process in the nuclear medium.
 Physics , 2002, Abstract: The coherent $\omega$-meson photoproduction from nuclei is proposed as a phenomenological method to evaluate the momentum dependence of $\omega$-meson mass shift and width in nuclear matter. We analyze available data on un-separated coherent and incoherent $\omega$-meson photoproduction from nuclei and extract the imaginary part of the the complex forward $\omega{N}$ scattering amplitude, which is proportional to the in-medium $\omega$-meson width. The accuracy of the currently available data is not sufficient to evaluate the real part of forward $\omega{N}$ scattering amplitude and reconstruct the momentum dependence of the mass shift of the $\omega$-meson.
 ALICE Collaboration Physics , 2015, Abstract: We report the first measurement at the LHC of coherent photoproduction of $\rho^0$ mesons in ultra-peripheral Pb-Pb collisions. The invariant mass and transverse momentum distributions for $\rho^0$ production are studied in the $\pi^+ \pi^-$ decay channel at mid-rapidity. The production cross section in the rapidity range $|y|<0.5$ is found to be $\mathrm{d}\sigma/\mathrm{d}y = 425 \pm 10 \, (\mathrm{stat.})$ $^{+42}_{-50} \, (\mathrm{sys.})$ mb. Coherent $\rho^0$ production is studied with and without requirement of nuclear breakup, and the fractional yields for various breakup scenarios are presented. The results are compared with those from lower energies and with model predictions based on the Glauber model and the color dipole model. The measured cross section is found to be inconsistent with a scaling of the $\gamma$-nucleon cross section using the Glauber model.
 B. Krusche Physics , 2011, DOI: 10.1140/epjst/e2011-01491-2 Abstract: Recent results for the photoproduction of mesons off nuclei are reviewed. These experiments have been performed for two major lines of research related to the properties of the strong interaction. The investigation of nucleon resonances requires light nuclei as targets for the extraction of the isospin composition of the electromagnetic excitations. This is done with quasi-free meson photoproduction off the bound neutron and supplemented with the measurement of coherent photoproduction reactions, serving as spin and/or isospin filters. Furthermore, photoproduction from light and heavy nuclei is a very efficient tool for the study of the interactions of mesons with nuclear matter and the in-medium properties of hadrons. Experiments are currently rapidly developing due to the combination of high quality tagged (and polarized) photon beams with state-of-the-art 4pi detectors and polarized targets.
 Physics , 1999, Abstract: In the last years much work has been done to learn about the properties of the $\rho$-meson in nuclear matter. In a calculation of the in-medium spectralfunction of the $\rho$ we find that it is strongly modified by baryonic resonances, especially the $D_{13}(1520)$, through its coupling to resonance-hole states. In order to test the predictions of a model for the in-medium properties of the $\rho$-meson so far mostly heavy-ion collision have been used. We argue that the coherent photoproduction of $\rho$-mesons yields additional information about the nature of the medium modification. It can be shown that the production amplitude is sensitive on the momentum dependence of the $\rho$-selfenergy. This can be used to distinguish experimentally between various models for the $\rho$ in matter.
 Physics , 2011, DOI: 10.1103/PhysRevC.85.014910 Abstract: Vector mesons may be photoproduced in relativistic heavy-ion collisions when a virtual photon emitted by one nucleus scatters from the other nucleus, emerging as a vector meson. The STAR Collaboration has previously presented measurements of coherent $\rho^0$ photoproduction at center of mass energies of 130 GeV and 200 GeV in AuAu collisions. Here, we present a measurement of the cross section at 62.4 GeV; we find that the cross section for coherent $\rho^0$ photoproduction with nuclear breakup is $10.5\pm1.5\pm 1.6$ mb at 62.4 GeV. The cross-section ratio between 200 GeV and 62.4 GeV is $2.8\pm0.6$, less than is predicted by most theoretical models. It is, however, proportionally much larger than the previously observed $15\pm 55$% increase between 130 GeV and 200 GeV.
 Physics , 1999, DOI: 10.1103/PhysRevC.62.014605 Abstract: In a transport model that combines initial state interactions of the photon with final state interactions of the produced particles we present a calculation of inclusive photoproduction of mesons in nuclei in the energy range from 1 to 7 GeV. We give predictions for the photoproduction cross sections of pions, etas, kaons, antikaons, and $\pi^+\pi^-$ invariant mass spectra in ^{12}C and ^{208}Pb. The effects of nuclear shadowing and final state interaction of the produced particles are discussed in detail.
 Page 1 /100 Display every page 5 10 20 Item