Эту проблему можно решить с помощью динамического программирования на деревьях, вы можете прочитать об этом здесь https://www.geeksforgeeks.org/dynamic-programming-trees-set-2/.
Разобьем задачу на две части, первая — найти количество допустимых путей в поддереве узла u
. Вторая часть — найти ответ для узла u
, если мы не рассматриваем его поддерево, а идем к его родителю и так далее.
Возьмем 1 за корень дерева.
Теперь для решения первой части мы создадим массив in[]
, в котором мы будем хранить количество путей в поддереве узла u
, поэтому in[u]
будет представлять количество допустимых путей, начинающихся с узла u
и посещающих его поддерево. Чтобы вычислить этот массив, мы можем запустить простой поиск в глубину следующим образом:
//u is the current node - p is the parent
void dfs1(int u, int p) {
for (int i = 0; i < g[u].size(); i++) { //iterate through the adjacency of node u
int v = g[u][i]; // v is the child of u
if (v != p) { //in case v is the parent just ignore it
dfs1(v, u); //go to node v
if (u >= k && v >= k) { //if value of u or v is less than k then we cant start at this node so it should be 0
in[u] += in[v] + 1; //add to number of paths of u the number of paths starting from the node v + 1 (+1 because we can also go from u to v)
}
}
}
}
Для решения второй части нам нужен массив out[]
, где out[u]
— количество допустимых путей, если мы не рассматриваем поддерево u
, которое ведет к родителю u
и так далее.
давайте позвоним родителю u
P[u]
. Чтобы вычислить out[u]
, мы будем полагаться на p[u]
. out[i]
— это число допустимых путей, если мы перейдем к p[u]
, и что мы можем сделать, когда доберемся до p[u]
, так это либо пройти через его поддерево (конечно, исключая ветвь u
), либо посетить p[p[u]]
(родитель родителя u
), поэтому out[u]
равно (out[p[u]] + 1) + (in[p[u]] - in[u] - 1)
.
// u is the current node - p is the parent
void dfs2(int u, int p) {
for (int i = 0; i < g[u].size(); i++) { // iterate through the adjacency of node u
int v = g[u][i]; // v is the child of u
if (v != p) { // in case v is the parent just ignore it
if (v >= k && u >= k) { // if value of u or v is less than k then we cant start at this node so it should be 0
out[v] += (out[u] + 1); //add to the number of paths of v the number of paths from it's parent (u) + 1 if we dont use the subtree of u
out[v] += (in[u] - in[v] - 1); // add to the number of paths of v the number of paths from it's parent (u)
// we should subtract in[v] + 1 because we want to exclude this branch from the subtree of the parent
}
dfs2(v, u); // go to node v
}
}
}
Чтобы найти ответ, просто просуммируйте все out[u] + in[u]
для всех узлов и разделите на 2, потому что каждый путь вычислялся дважды.
сложность O(V+E)
person
Walid
schedule
10.02.2019
nC2
, гдеn
— это общее количество узлов в этом отдельном пути. - person taurus05   schedule 10.02.2019root node to child node
. - person taurus05   schedule 10.02.20195C2
. - person taurus05   schedule 10.02.2019x
к остальным узлам и, если узелx
был частью цикла, то длина пути был бы бесконечен, если бы он удовлетворял всем ограничениям. Следовательно, это определенно дерево. Ни при каких обстоятельствах это не будет график. - person taurus05   schedule 11.02.2019f
иa, b& c
. - person taurus05   schedule 12.02.2019