problem link这是关于从图形中移除最多两个边，并使拆分中的顶点数乘积最大的问题。在这个问题中，我们给出了一个具有（N + 1）个节点和N个边的树图。我们应该返回子树大小乘积的最大结果。如果原始树图未拆分，则值为N +1。如果树图拆分为两个子树（删除了一个边），则结果为X * Y的最大值（X，Y为大小的子树）。如果拆分为三个子树，则结果为X * Y * Z的最大值。我们应该返回通过三种拆分方法可以获得的最大结果/乘积。两个子树的情况很简单。对于三个子树的情况，假定的最差时间为O（nlogn），空间为O（n）。登录的时间让我想起了二进制搜索或两分支树。但是，在此问题中，不能保证树是两分支的，因此深度可能大于logn。蛮力似乎带来了很大的时间复杂性，我认为这个问题可能与树和图中的一些经典算法模式有关，这可能使其很容易解决，也可能是正确的解决方法有这样的问题。我从堆栈溢出中看到了HilbertMaze的答案，这对我有很大帮助。我希望有人急于解决新问题，并提出一个很棒的解决方案供我们学习！
public String solution(int[] A, int[] B) {
Node[] guardPostArray = new Node[A.length + 1];
for (int i = 0; i < A.length; i++) {
Node first = guardPostArray[A[i]];
if (first == null) {
first = new Node(A[i]);
guardPostArray[A[i]] = first;
}
Node second = guardPostArray[B[i]];
if (second == null) {
second = new Node(B[i]);
guardPostArray[B[i]] = second;
}
first.edges.add(B[i]);
second.edges.add(A[i]);
}
Node root = createTree(guardPostArray);
int split = root.heviestChild.weight;
long max = guardPostArray.length;
max = (long) Math.max(max, (guardPostArray.length - split) * split);
max = Math.max(max, bestTrisplit(root, guardPostArray));
return "" + max;
}
public int[] sortedSet(Set<Integer> set) {
int[] res = new int[set.size()];
int i = 0;
for (Integer integer : set.toArray(new Integer[0])) {
res[i] = integer;
i++;
}
Arrays.sort(res);
return res;
}
public long bestTrisplit(Node root, Node[] guardPostArray) {
Set<Integer> heavyCuts = new HashSet<>();
heavyCuts.add(1);
Set<Integer> otherCuts = new HashSet<>();
otherCuts.add(1);
for (Node child : root.childs) {
if (child.weight == 1) {
continue;
}
if (child == root.heviestChild) {
// child.postOrder(c -> heavyCuts.add(c.weight));
child.postOrder(heavyCuts);
} else {
// child.postOrder(c -> otherCuts.add(c.weight));
child.postOrder(otherCuts);
}
}
int[] heavyCutsArray = sortedSet(heavyCuts);
int[] otherCutsArray = sortedSet(otherCuts);
// int[] heavyCutsArray = heavyCuts.stream().mapToInt(i -> i).sorted().toArray();
// int[] otherCutsArray = otherCuts.stream().mapToInt(i -> i).sorted().toArray();
Node heavyChild = root.heviestChild;
double middle = heavyChild.weight / 2.0;
long closestToMiddle = closestTo(heavyCutsArray, middle);
long bestTriple = closestToMiddle * (heavyChild.weight - closestToMiddle) * (root.weight - heavyChild.weight);
for (int i = heavyCutsArray.length - 1; i >= 0; i--) {
middle = (root.weight - heavyCutsArray[i]) / 2.0;
closestToMiddle = closestTo(otherCutsArray, middle);
long trisec = closestToMiddle * heavyCutsArray[i] * (root.weight - heavyCutsArray[i] - closestToMiddle);
bestTriple = Math.max(bestTriple, trisec);
if (heavyCutsArray[i] < Math.min(closestToMiddle, root.weight - heavyCutsArray[i] - closestToMiddle)) {
break;
}
}
return bestTriple;
}
public int closestTo(int[] sortedArray, double value) {
int lower = 0;
int upper = sortedArray.length - 1;
if (sortedArray.length == 1) {
return sortedArray[0];
}
while (lower <= upper) {
int mid = (lower + upper) / 2;
if (value < sortedArray[mid]) {
upper = mid - 1;
} else if (value > sortedArray[mid]) {
lower = mid + 1;
} else {
return sortedArray[mid];
}
}
if (lower == sortedArray.length) {
return sortedArray[lower - 1];
}
return Math.abs(sortedArray[lower] - value) < Math.abs(sortedArray[lower - 1] - value) ? sortedArray[lower] : sortedArray[lower - 1];
}
private Node createTree(Node[] nodesArray) {
int minRootWeight = (nodesArray.length / 2) + 1;// If we find a node this size, make it the root
LinkedList<Node> queue = new LinkedList<>();
for (Node guardPost : nodesArray) {
if (guardPost.edges.size() == 1) {
queue.add(guardPost);
}
}
while (queue.size() > 1) {
Node g = queue.poll();
// assert g.edges.size() == 1 : "node " + g.id + " processed as leaf but has " + g.edges.size() + " edges left";
if (g.weight < minRootWeight) {
Integer parentId = g.edges.getFirst();
Node parent = nodesArray[parentId];
g.setParent(parent);
parent.addSubTree(g);
if (parent.heviestChild == null || parent.heviestChild.weight < g.weight) {
parent.heviestChild = g;
}
if (parent.edges.size() == 1) {
queue.addLast(parent);
}
} else {
queue.addLast(g);
}
}
Node root = queue.poll();
// if (root.childs.isEmpty()) {
// throw new RuntimeException("root don't have edges");
// }
// if (root.weight != nodesArray.length) {
// throw new RuntimeException("root is not connected to all other nodes.!");
// }
// if (root.childs.stream().anyMatch(child -> child.weight > nodesArray.length / 2)) {
// throw new RuntimeException("root has child heavier than n/2!");
// }
return root;
}
class Node {
LinkedList<Integer> edges;
LinkedList<Node> childs;
int id;
boolean dontCount = false;
Node parent;
Node heviestChild;
int weight = 1;
public Node(int id) {
this.edges = new LinkedList<>();
this.id = id;
childs = new LinkedList<>();
}
public void postOrder(Consumer<Node> func) {
for (Node child : childs) {
child.postOrder(func);
}
func.accept(this);
}
public void postOrder(Set<Integer> set) {
for (Node child : childs) {
child.postOrder(set);
}
set.add(this.weight);
}
public void setParent(Node parent) {
if (!edges.remove(new Integer(parent.id))) {
throw new RuntimeException("parent " + id + " is not in edges");
}
this.parent = parent;
}
// For building the tree. Attaches a subtree to this node.
// Every path from the subtree to any other node goes through self.
public void addSubTree(Node node) {
if (!edges.remove(new Integer(node.id))) {
throw new RuntimeException("Adding unrecognized child " + node.id + "to node " + id + "}");
}
childs.add(node);
weight += node.weight;
}
@Override
public String toString() {
return "N{" + "id=" + id + " children=" + childs.toString() + '}';
}
}