

Revision History 

Subtrees(vertices) of a given rooted tree
The problem involves a rooted tree. Sometimes a graph is given and its DFS search tree is used. Some sort of result can be calculated for each subtree. Since each subtree is uniquely identified by its root, we can treat DP over subtrees as DP over vertices. The result for each nonleaf vertex is determined by the results of its immediate children.
The DP over subtree has a state domain in form (v,a) where v is a root of subtree and "a" may be some additional parameters. states are ordered naturally be tree order on vertices. Therefore the easiest way to iterate through states in correct order is to launch DFS from the root of tree. When DFS exits from a vertex, its result must be finally computed and stored in global memory. The code generally looks like:
bool vis[N]; //visited mark for DFS
res[N]; //DP result array
void DFS(int v) { //visit vrooted subtree recursively
vis[v] = true; //mark vertex as visited
res[v] = ???; //initial result, which is final result in case v is leaf
for (int i = 0; i<nbr[v].size(); i++) { //iterate through all sons s
int s = nbr[v][i];
if (!vis[s]) { //if vertex is not visited yet, then it's a son in DFS tree
DFS(s); //visit it recursively
res[v] = DPInduction(res[v], res[s]); //recalculate result for current vertex
}
}
}
...
memset(vis, false, sizeof(vis)); //mark all vertices as not visited
DFS(0); //run DFS from the root = vertex 0
answer = DPAnswer(res[0]); //get problem answer from result of root
Sometimes the graph of problem is not connected (e.g. a forest). In this case run a series of DFS over the whole graph. The results for roots of individual trees are then combined in some way. Usually simple summation/maximum or a simple formula is enough but in tough cases this "merging problem" can turn out to require another DP solution.
The DPInduction is very simple in case when there are no additional parameters. But very often state domain includes the additional parameters and becomes complicated. DPInduction turns out to be another(internal) DP in this case. Its state domain is (k,a) where k is number of sons of vertex considered so far and "a" is additional info. Be careful about the storage of results of this internal DP. If you are solving optimization problem and you are required to recover the solution (not only answer) then you have to save results of this DP for solution recovering. In this case you'll have an array globalres[v,a] and an array internalres[v,k,a]. Topcoder problems rarely require solution, so storage of internal DP results is not necessary. It is easier not to store them globally. In the code below internal results for a vertex are initialized after all the sons are traversed recursively and are discarded after DFS exits a vertex. This case is represented in the code below:
bool vis[N];
gres[N][A];
intres[N+1][A];
void DFS(int v) {
vis[v] = true;
vector<int> sons;
for (int i = 0; i<nbr[v].size(); i++) { //first pass: visit all sons and store their indices
int s = nbr[v][i];
if (!vis[s]) {
DFS(s);
sons.push_back(s);
}
}
int SK = sons.size(); //clear the internal results array
for (int k = 0; k<=SK; k++)
memset(intres[k], ?, sizeof(intres[k]));
for (int a = 0; a<A; a++) //second pass: run internal DP over array of sons
intres[0][a] = InternalDPBase(v, a);
for (int k = 0; k<SK; k++) //k = number of sons considered so far
for (int a = 0; a<A; a++) //a = additional parameter for them
for (int b = 0; b<A; b++) { //b = additional parameter for the son being added
int na = DPTransition(v, a, b);
int nres = DPInduction(intres[k][a], gres[sons[k]][b]);
intres[k+1][na] = DPMerge(intres[k+1][na], nres);
}
for (int a = 0; a<A; a++) //copy answer of internal DP to result for vertex
gres[v][a] = intres[SK][a];
}
...
memset(vis, false, sizeof(vis)); //series of DFS
for (int v = 0; v<N; v++) if (!vis[v]) {
DFS(v);
??? //handle results for connected component
}
??? //get the answer in some way
It is very important to understand how time/space complexity is calculated for DP over subtrees. For example, the code just above requires O(N*A^2) time. Though dumb analysis says it is O(N^2*A^2): {N vertices} x {SK<=N sons for each} x A x A. Let Ki denote number of sons of vertex i. Though each Ki may be as large as N1, their sum is always equal to N1 in a rooted tree. This fact is the key to further analysis. Suppose that DFS code for ith vertex runs in not more than Ki*t time. Since DFS is applied only once to each vertex, the overall time will be TC(N) = sum(Ki*t) <= N*t. Consider t=A^2 for the case above and you'll get O(N*A^2) time complexity. To benefit from this acceleration, be sure not to iterate through all vertices of graph in DFS. For example above, running memset for the whole intres array in DFS will raise the time complexity. Time of individual DFS run will become O(N*A + Ki*A^2) instead of O(Ki*A^2). The overall time complexity will become O(N^2*A + N*A^2) which is great regress in case if A is much smaller that N. Using the same approach you may achieve O(N*A) space complexity in case you are asked to recover solution. We have already said that to recover solution you have to store globally the array internalres[v,k,a]. If you allocate memory for this array dynamically, then you can ignore completely states with k>Ki. Since the sum of all Ki is N, you will get O(N*A) space.


Subtrees(vertices) of a given rooted tree
The problem involves a rooted tree. Sometimes a graph is given and its DFS search tree is used. Some sort of result can be calculated for each subtree. Since each subtree is uniquely identified by its root, we can treat DP over subtrees as DP over vertices. The result for each nonleaf vertex is determined by the results of its immediate children.
The DP over subtree has a state domain in form (v,a) where v is a root of subtree and a may be some additional parameters. states are ordered naturally be tree order on vertices. Therefore the easiest way to iterate through states in correct order is to launch DFS from the root of tree. When DFS exits from a vertex, its result must be finally computed and stored in global memory. The code generally looks like:
bool vis[N]; //visited mark for DFS
res[N]; //DP result array
void DFS(int v) { //visit vrooted subtree recursively
vis[v] = true; //mark vertex as visited
res[v] = ???; //initial result, which is final result in case v is leaf
for (int i = 0; i<nbr[v].size(); i++) { //iterate through all sons s
int s = nbr[v][i];
if (!vis[s]) { //if vertex is not visited yet, then it's a son in DFS tree
DFS(s); //visit it recursively
res[v] = DPInduction(res[v], res[s]); //recalculate result for current vertex
}
}
}
...
memset(vis, false, sizeof(vis)); //mark all vertices as not visited
DFS(0); //run DFS from the root = vertex 0
answer = DPAnswer(res[0]); //get problem answer from result of root
Sometimes the graph of problem is not connected (e.g. a forest). In this case run a series of DFS over the whole graph. The results for roots of individual trees are then combined in some way. Usually simple summation/maximum or a simple formula is enough but in tough cases this "merging problem" can turn out to require another DP solution.
The DPInduction is very simple in case when there are no additional parameters. But very often state domain includes the additional parameters and becomes complicated. DPInduction turns out to be another(internal) DP in this case. Its state domain is (k,a) where k is number of sons of vertex considered so far and a is additional info. Be careful about the storage of results of this internal DP. If you are solving optimization problem and you are required to recover the solution (not only answer) then you have to save results of this DP for solution recovering. In this case you'll have an array globalres[v,a] and an array internalres[v,k,a]. Topcoder problems rarely require solution, so storage of internal DP results is not necessary. It is easier not to store them globally. In the code below internal results for a vertex are initialized after all the sons are traversed recursively and are discarded after DFS exits a vertex. This case is represented in the code below:
bool vis[N];
gres[N][A];
intres[N+1][A];
void DFS(int v) {
vis[v] = true;
vector<int> sons;
for (int i = 0; i<nbr[v].size(); i++) { //first pass: visit all sons and store their indices
int s = nbr[v][i];
if (!vis[s]) {
DFS(s);
sons.push_back(s);
}
}
int SK = sons.size(); //clear the internal results array
for (int k = 0; k<=SK; k++)
memset(intres[k], ?, sizeof(intres[k]));
for (int a = 0; a<A; a++) //second pass: run internal DP over array of sons
intres[0][a] = InternalDPBase(v, a);
for (int k = 0; k<SK; k++) //k = number of sons considered so far
for (int a = 0; a<A; a++) //a = additional parameter for them
for (int b = 0; b<A; b++) { //b = additional parameter for the son being added
int na = DPTransition(v, a, b);
int nres = DPInduction(intres[k][a], gres[sons[k]][b]);
intres[k+1][na] = DPMerge(intres[k+1][na], nres);
}
for (int a = 0; a<A; a++) //copy answer of internal DP to result for vertex
gres[v][a] = intres[SK][a];
}
...
memset(vis, false, sizeof(vis)); //series of DFS
for (int v = 0; v<N; v++) if (!vis[v]) {
DFS(v);
??? //handle results for connected component
}
??? //get the answer in some way
It is very important to understand how time/space complexity is calculated for DP over subtrees. For example, the code just above requires O(N*A^2) time. Though dumb analysis says it is O(N^2*A^2): {N vertices} x {SK<=N sons for each} x A x A. Let Ki denote number of sons of vertex i. Though each Ki may be as large as N1, their sum is always equal to N1 in a rooted tree. This fact is the key to further analysis. Suppose that DFS code for ith vertex runs in not more than Ki*t time. Since DFS is applied only once to each vertex, the overall time will be TC(N) = sum(Ki*t) <= N*t. Consider t=A^2 for the case above and you'll get O(N*A^2) time complexity. To benefit from this acceleration, be sure not to iterate through all vertices of graph in DFS. For example above, running memset for the whole intres array in DFS will raise the time complexity. Time of individual DFS run will become O(N*A + Ki*A^2) instead of O(Ki*A^2). The overall time complexity will become O(N^2*A + N*A^2) which is great regress in case if A is much smaller that N. Using the same approach you may achieve O(N*A) space complexity in case you are asked to recover solution. We have already said that to recover solution you have to store globally the array internalres[v,k,a]. If you allocate memory for this array dynamically, then you can ignore completely states with k>Ki. Since the sum of all Ki is N, you will get O(N*A) space.


Subtrees(vertices) of a given rooted tree
The problem involves a rooted tree. Sometimes a graph is given and its DFS search tree is used. Some sort of result can be calculated for each subtree. Since each subtree is uniquely identified by its root, we can treat DP over subtrees as DP over vertices. The result for each nonleaf vertex is determined by the results of its immediate children.
The DP over subtree has a state domain in form (v,a) where v is a root of subtree and a may be some additional parameters. states are ordered naturally be tree order on vertices. Therefore the easiest way to iterate through states in correct order is to launch DFS from the root of tree. When DFS exits from a vertex, its result must be finally computed and stored in global memory. The code generally looks like:
bool vis[N]; //visited mark for DFS
res[N]; //DP result array
void DFS(int v) { //visit vrooted subtree recursively
vis[v] = true; //mark vertex as visited
res[v] = ?; //initial result, which is final result in case v is leaf
for (int i = 0; i<nbr[v].size(); i++) { //iterate through all sons s
int s = nbr[v][i];
if (!vis[s]) { //if vertex is not visited yet, then it's a son in DFS tree
DFS(s); //visit it recursively
res[v] = DPInduction(res[v], res[s]); //recalculate result for current vertex
}
}
}
...
memset(vis, false, sizeof(vis)); //mark all vertices as not visited
DFS(0); //run DFS from the root = vertex 0
answer = DPAnswer(res[0]); //get problem answer from result of root
Sometimes the graph of problem is not connected (e.g. a forest). In this case run a series of DFS over the whole graph. The results for roots of individual trees are then combined in some way. Usually simple summation/maximum or a simple formula is enough but in tough cases this "merging problem" can turn out to require another DP solution.
The DPInduction is very simple in case when there are no additional parameters. But very often state domain includes the additional parameters and becomes complicated. DPInduction turns out to be another(internal) DP in this case. Its state domain is (k,a) where k is number of sons of vertex considered so far and a is additional info. Be careful about the storage of results of this internal DP. If you are solving optimization problem and you are required to recover the solution (not only answer) then you have to save results of this DP for solution recovering. In this case you'll have an array globalres[v,a] and an array internalres[v,k,a]. Topcoder problems rarely require solution, so storage of internal DP results is not necessary. It is easier not to store them globally. In the code below internal results for a vertex are initialized after all the sons are traversed recursively and are discarded after DFS exits a vertex. This case is represented in the code below:
bool vis[N];
gres[N][A];
intres[N+1][A];
void DFS(int v) {
vis[v] = true;
vector<int> sons;
for (int i = 0; i<nbr[v].size(); i++) { //first pass: visit all sons and store their indices
int s = nbr[v][i];
if (!vis[s]) {
DFS(s);
sons.push_back(s);
}
}
int SK = sons.size(); //clear the internal results array
for (int k = 0; k<=SK; k++)
memset(intres[k], ?, sizeof(intres[k]));
for (int a = 0; a<A; a++) //second pass: run internal DP over array of sons
intres[0][a] = InternalDPBase(v, a);
for (int k = 0; k<SK; k++) //k = number of sons considered so far
for (int a = 0; a<A; a++) //a = additional parameter for them
for (int b = 0; b<A; b++) { //b = additional parameter for the son being added
int na = DPTransition(v, a, b);
int nres = DPInduction(intres[k][a], gres[sons[k]][b]);
intres[k+1][na] = DPMerge(intres[k+1][na], nres);
}
for (int a = 0; a<A; a++) //copy answer of internal DP to result for vertex
gres[v][a] = intres[SK][a];
}
...
memset(vis, false, sizeof(vis)); //series of DFS
for (int v = 0; v<N; v++) if (!vis[v]) {
DFS(v);
??? //handle results for connected component
}
??? //get the answer in some way
It is very important to understand how time/space complexity is calculated for DP over subtrees. For example, the code just above requires O(N*A^2) time. Though dumb analysis says it is O(N^2*A^2): {N vertices} x {SK<=N sons for each} x A x A. Let Ki denote number of sons of vertex i. Though each Ki may be as large as N1, their sum is always equal to N1 in a rooted tree. This fact is the key to further analysis. Suppose that DFS code for ith vertex runs in not more than Ki*t time. Since DFS is applied only once to each vertex, the overall time will be TC(N) = sum(Ki*t) <= N*t. Consider t=A^2 for the case above and you'll get O(N*A^2) time complexity. To benefit from this acceleration, be sure not to iterate through all vertices of graph in DFS. For example above, running memset for the whole intres array in DFS will raise the time complexity. Time of individual DFS run will become O(N*A + Ki*A^2) instead of O(Ki*A^2). The overall time complexity will become O(N^2*A + N*A^2) which is great regress in case if A is much smaller that N. Using the same approach you may achieve O(N*A) space complexity in case you are asked to recover solution. We have already said that to recover solution you have to store globally the array internalres[v,k,a]. If you allocate memory for this array dynamically, then you can ignore completely states with k>Ki. Since the sum of all Ki is N, you will get O(N*A) space.

