Viz Zadání.

Úloha chce, abychom v obecném kořenovém stromu s obarvenými uzly našli co nejdelší monochromatickou cestu.

Myšlenka řešení:

Průchod postorder, v každém uzlu shromažďujeme informaci o délkách monochromatických cest vedoucích zespoda do tohoto uzlu, a to pouze o těch, jejichž barva souhlasí s barvou aktuálního uzlu. Pokud nám vychází cesta dosud nejdelší, zapamatujeme si ji. Tato nejdelší se skládá buď ze dvou větví vycházejících dolů z tohoto uzlu nebo z větve jediné. Délku nejdelší monochromatické větve té barvy, kterou má rodič, pošleme v postrorderu nahoru do rodiče.

Strom není nutno stavět, je reprezentován vhodně pro průchod postorder rovnou ve vstupních datech.

package alg;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main {
 
    static Node root;
    static int bestLength;
    static Set<Integer> bestAttrs;
 
    public static class Node {
        int attr;
        int localBest;
        int directBest;
        int numOfNodes;
        List<Node> children;
 
        public Node(int attr) {
            this.attr = attr;
            localBest = 0;
            directBest = 0;
            numOfNodes = 0;
            children = new ArrayList<Node>();
        }
    }
 
    private static void loadChildren(Node node, BufferedReader reader) throws IOException {
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        String str = tokenizer.nextToken();
        while (!str.equals(")")) {
            int attr = Integer.valueOf(str);
            Node child = new Node(attr);
            node.children.add(child);
            loadChildren(child, reader);
            tokenizer = new StringTokenizer(reader.readLine());
            str = tokenizer.nextToken();
        }
    }
 
    public static void loadData() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        String str = tokenizer.nextToken();
        int attr = Integer.valueOf(str);
        root = new Node(attr);
        loadChildren(root, reader);
    }
 
    public static void postOrder(Node node) {
        int first = 0;
        int second = 0;
        node.numOfNodes = 1;
        for (Node child : node.children) {
            postOrder(child);
            if (child.attr == node.attr) {
                if (child.directBest > first) {
                    second = first;
                    first = child.directBest;
                } else if (child.directBest > second) {
                    second = child.directBest;
                }
            }
            node.numOfNodes += child.numOfNodes;
        }
        node.localBest = 1 + first + second;
        node.directBest = 1 + first;
        if (node.localBest > bestLength) {
            bestAttrs.clear();
            bestLength = node.localBest;
            bestAttrs.add(node.attr);
        } else if (node.localBest == bestLength) {
            bestAttrs.add(node.attr);
        }
    }
 
    public static void solve() {
        bestLength = 0;
        bestAttrs = new HashSet<Integer>();
        postOrder(root);
        System.out.println(bestLength);
        List<Integer> bestAttrsList = new ArrayList<Integer>(bestAttrs);
        Collections.sort(bestAttrsList);
        for (int i = 0; i < bestAttrsList.size(); i++) {
            System.out.print(bestAttrsList.get(i));
            if (i < bestAttrsList.size() - 1)
                System.out.print(" ");
            }
    }
 
    public static void main(String[] args) throws IOException {
        loadData();
        solve();
    }
}