{"id":5245,"date":"2020-10-03T19:03:22","date_gmt":"2020-10-03T16:03:22","guid":{"rendered":"http:\/\/java.mazurok.com\/?p=5245"},"modified":"2020-11-25T12:17:46","modified_gmt":"2020-11-25T09:17:46","slug":"e-olymp-9414-%d1%83%d0%b1%d0%b8%d1%82%d1%8c-%d0%b2%d1%81%d0%b5%d1%85-%d1%82%d0%b5%d1%80%d0%bc%d0%b8%d1%82%d0%be%d0%b2","status":"publish","type":"post","link":"https:\/\/java.mazurok.com\/?p=5245","title":{"rendered":"e-olymp 9414. \u0423\u0431\u0438\u0442\u044c \u0432\u0441\u0435\u0445 \u0442\u0435\u0440\u043c\u0438\u0442\u043e\u0432"},"content":{"rendered":"<h1>\u0423\u0441\u043b\u043e\u0432\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438<\/h1>\n<p>\u041d\u0430 \u0434\u0435\u0440\u0435\u0432\u0435 \u0436\u0438\u0432\u0443\u0442 \u0442\u0435\u0440\u043c\u0438\u0442\u044b. \u0412\u0430\u0448\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u0443\u0431\u0438\u0442\u044c \u0438\u0445 \u0432\u0441\u0435\u0445. \u0414\u0435\u0440\u0435\u0432\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u0441\u0432\u044f\u0437\u043d\u044b\u043c \u0433\u0440\u0430\u0444\u043e\u043c \u0441 $n$ \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438 \u0438 $n &#8212; 1$ \u0440\u0435\u0431\u0440\u0430\u043c\u0438. \u0427\u0442\u043e\u0431\u044b \u0443\u0431\u0438\u0442\u044c \u0442\u0435\u0440\u043c\u0438\u0442\u043e\u0432, \u0412\u0430\u043c \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u043e\u0442\u0440\u0430\u0432\u0438\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b. \u0415\u0441\u043b\u0438 \u0442\u0435\u0440\u043c\u0438\u0442 \u043f\u043e\u043f\u0430\u0434\u0430\u0435\u0442 \u043d\u0430 \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0441 \u044f\u0434\u043e\u043c, \u0442\u043e \u043e\u043d \u043d\u0435\u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e \u0443\u043c\u0438\u0440\u0430\u0435\u0442. \u0412\u044b \u043d\u0435 \u0437\u043d\u0430\u0435\u0442\u0435, \u0433\u0434\u0435 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0442\u0435\u0440\u043c\u0438\u0442\u044b. \u041d\u043e \u0412\u044b \u0437\u043d\u0430\u0435\u0442\u0435, \u0447\u0442\u043e \u0442\u0435\u0440\u043c\u0438\u0442\u044b \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u043f\u043e\u043f\u0430\u0434\u0430\u044e\u0442 \u0432 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u0443\u044e \u0441\u043e\u0441\u0435\u0434\u043d\u044e\u044e \u0432\u0435\u0440\u0448\u0438\u043d\u0443. \u041e\u0434\u043d\u0430\u043a\u043e \u0435\u0441\u043b\u0438 \u0442\u0435\u0440\u043c\u0438\u0442 \u043f\u0440\u043e\u0448\u0435\u043b \u0440\u0435\u0431\u0440\u043e $(u, v)$, \u0442\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u0440\u0435\u0431\u0440\u043e \u0434\u043e\u043b\u0436\u043d\u043e \u043e\u0442\u043b\u0438\u0447\u0430\u0442\u044c\u0441\u044f \u043e\u0442 $(v, u)$ \u0437\u0430 \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u044f, \u043a\u043e\u0433\u0434\u0430 \u0442\u0435\u0440\u043c\u0438\u0442 \u043f\u043e\u043f\u0430\u0434\u0430\u0435\u0442 \u0432 \u043b\u0438\u0441\u0442 (\u0432 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0442\u0435\u0440\u043c\u0438\u0442 \u043f\u043e\u0432\u043e\u0440\u0430\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u043d\u0430\u0437\u0430\u0434). \u0412\u0430\u043c \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u043e\u0442\u0440\u0430\u0432\u0438\u0442\u044c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u0440\u0448\u0438\u043d \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0442\u0435\u0440\u043c\u0438\u0442\u044b \u043f\u043e\u043f\u0430\u043b\u0438 \u0432 \u043e\u0442\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043f\u043e\u0441\u043b\u0435 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0448\u0430\u0433\u043e\u0432.<\/p>\n<h1>\u0412\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435<\/h1>\n<p>\u041f\u0435\u0440\u0432\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043e\u0434\u043d\u043e \u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e $n$ $(1 \\leqslant n \\leqslant 100000)$. \u0421\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 $n &#8212; 1$ \u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e\u00a0 $p_{i} (2 \\leqslant i \\leqslant n)$, \u043e\u0437\u043d\u0430\u0447\u0430\u044e\u0449\u0435\u0435 \u0447\u0442\u043e \u0440\u0435\u0431\u0440\u043e \u0441\u043e\u0435\u0434\u0438\u043d\u044f\u0435\u0442 $p_{i}$ \u0438 $i$.<\/p>\n<h1>\u0412\u044b\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435<\/h1>\n<p>\u0412\u044b\u0432\u0435\u0434\u0438\u0442\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0442\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d.<\/p>\n<h1>\u0422\u0435\u0441\u0442\u044b<\/h1>\n<table>\n<tbody>\n<tr>\n<td>\u2116<\/td>\n<td>\u0412\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435<\/td>\n<td>\u0412\u044b\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435<\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>2<\/td>\n<td>2<br \/>\n1<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>3<\/td>\n<td>8<br \/>\n1 1 2 1 2 3 2<\/td>\n<td>2<\/td>\n<\/tr>\n<tr>\n<td>4<\/td>\n<td>5<br \/>\n1 2 1 4<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>5<\/td>\n<td>16<br \/>\n1 2 3 4 5 3 7 1 9 9 11 11 13 13 15<\/td>\n<td>3<\/td>\n<\/tr>\n<tr>\n<td>6<\/td>\n<td>10<br \/>\n1 2 3 3 1 2 3 7 9<\/td>\n<td>2<\/td>\n<\/tr>\n<tr>\n<td>7<\/td>\n<td>8<br \/>\n1 1 3 3 1 6 6<\/td>\n<td>2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h1>\u041a\u043e\u0434<\/h1>\n<pre class=\"lang:java decode:true\">import java.util.ArrayList;\r\nimport java.util.LinkedList;\r\nimport java.util.Queue;\r\nimport java.util.Scanner;\r\n\r\npublic class Main {\r\n    static final int NMAX = 100001;\r\n    static ArrayList&lt;ArrayList&lt;Integer&gt;&gt; tree = new ArrayList&lt;ArrayList&lt;Integer&gt;&gt; (NMAX);\r\n    static ArrayList&lt;Integer&gt; killed = new ArrayList&lt;Integer&gt; (NMAX);\r\n    static ArrayList&lt;Boolean&gt; used = new ArrayList&lt;Boolean&gt; (NMAX);\r\n    static ArrayList&lt;Integer&gt; dist = new ArrayList&lt;Integer&gt; (NMAX);\r\n    static int ans = 0;\r\n\r\n    public static void kills(int v, int p)\r\n    {\r\n        if (v == p) kills(tree.get(v).get(0), v);\r\n        if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) kills(to, v);\r\n        if (tree.get(v).size() &gt;= 3) killed.set(v, killed.get(v) + 1);\r\n        return;\r\n    }\r\n\r\n    public static void goup(int v, int p)\r\n    {\r\n        if (v == p)\r\n        {\r\n            for (Integer to : tree.get(v)) if (dist.get(to) &lt; dist.get(v)) goup(to, v);\r\n            killed.set(v, 0);\r\n            return;\r\n        }\r\n        if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) goup(to, v);\r\n        if (tree.get(v).size() &gt;= 3)\r\n        {\r\n            killed.set(v, killed.get(v) + 1);\r\n            return;\r\n        }\r\n    }\r\n\r\n    public static void main(String[] args) {\r\n        Scanner in = new Scanner(System.in);\r\n        for (int i=0;i&lt;NMAX; i++)\r\n        {\r\n            tree.add(new ArrayList&lt;Integer&gt;());\r\n            dist.add(0);\r\n            used.add(false);\r\n            killed.add(0);\r\n        }\r\n        int n,v;\r\n        n = in.nextInt();\r\n        if (n &lt;= 5) {System.out.print(1); return;} \/\/ \u0427\u0430\u0441\u0442\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439\r\n        tree.get(1).add(0); \/\/ \u041a\u043e\u0440\u0435\u043d\u044c \u0442\u043e\u0436\u0435 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \"\u0440\u0430\u0437\u0432\u0438\u043b\u043a\u043e\u0439\"\r\n        ArrayList&lt;Integer&gt; leaves = new ArrayList&lt;Integer&gt; ();\r\n        for (int i = 1; i &lt; n; i++)\r\n        {\r\n            v = in.nextInt();\r\n            tree.get(v).add(i+1);\r\n            tree.get(i+1).add(v); \/\/\u0417\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0433\u0440\u0430\u0444\u0430 \u0432 \u0442\u043e\u043c \u0432\u0438\u0434\u0435, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0435\u0433\u043e \u0434\u0430\u044e\u0442\r\n        }\r\n\r\n        for (int i = 1; i &lt;= n; i++)\r\n        {\r\n            if (tree.get(i).size() == 1 || (i == 1 &amp;&amp; tree.get(i).size() == 2)) leaves.add(i); \/\/\u0417\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u0435\u043c \u0432\u0441\u0435 \u043b\u0438\u0441\u0442\u044c\u044f\r\n        }\r\n\r\n        LinkedList&lt;Integer&gt; q = new LinkedList&lt;&gt;(); dist.set(1, 0);\r\n        q.offer(1); used.set(1, true);\r\n        while (!q.isEmpty())\r\n        {\r\n            int qv = q.poll();\r\n            used.set(qv, true);\r\n            for (Integer to : tree.get(qv))                \/\/BFS \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u044e\u0449\u0438\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 dist\r\n            {\r\n                if (!used.get(to))\r\n                {\r\n                    q.offer(to);\r\n                    dist.set(to, dist.get(qv)+1);\r\n                }\r\n            }\r\n        }\r\n\r\n        for (Integer l : leaves)\r\n        {\r\n            kills(l, l);        \/\/ \u041f\u0435\u0440\u0432\u044b\u0439 \u044d\u0442\u0430\u043f - \u0437\u0430\u043f\u0440\u043e\u0441\u044b \u043e\u0442 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043b\u0438\u0441\u0442\u0430\r\n        }\r\n\r\n        int maxdist = -1; for (int i = 1; i &lt;= n; i++) maxdist = Math.max(maxdist, dist.get(i)); \/\/ \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \"\u0443\u0440\u043e\u0432\u043d\u044f\" \u0434\u0435\u0440\u0435\u0432\u0430\r\n        int wentup = 1;\r\n        while (wentup != 0)\r\n        {\r\n            wentup = 0;\r\n            for (int l = maxdist; l &gt; 0; l--)\r\n            {\r\n                for (int i = 2; i &lt;= n; i++)\r\n                {\r\n                    if (killed.get(i) == 1 &amp;&amp; dist.get(i) == l)\r\n                    {\r\n                        goup(i, i);                    \/\/\u042d\u0442\u0430\u043f 2 - \u043f\u043e\u0434\u043d\u044f\u0442\u0438\u0435 \"\u043d\u0435\u0434\u043e\u0448\u0435\u0434\u0448\u0438\u0445\" \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432\r\n                        wentup++;\r\n                    }\r\n                }\r\n            }\r\n        }\r\n        for (int i = 1; i &lt;= n; i++) if (killed.get(i) &gt;= 2) ans++; \/\/\u0424\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u043e\u0434\u0441\u0447\u0435\u0442 \"\u043e\u0442\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0445\" \u0440\u0430\u0437\u0432\u0438\u043b\u043e\u043a\r\n        System.out.print(ans);\r\n    }\r\n}<\/pre>\n<h1>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438<\/h1>\n<p>\u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0432 \u0437\u0430\u0434\u0430\u0447\u0435 \u0440\u0435\u0447\u044c \u0438\u0434\u0435\u0442 \u043e \u0434\u0435\u0440\u0435\u0432\u0435, \u0446\u0438\u043a\u043b\u043e\u0432 \u0432 \u043d\u0435\u043c \u043d\u0435\u0442 \u043f\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044e. \u0417\u043d\u0430\u0447\u0438\u0442, \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u043c \u0434\u043b\u044f \u0442\u0435\u0440\u043c\u0438\u0442\u0430 \u0445\u043e\u0434\u0438\u0442\u044c &#171;\u0432\u0435\u0447\u043d\u043e&#187; \u0431\u0443\u0434\u0435\u0442 \u043f\u0443\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u043b\u0438\u0441\u0442\u0430\u043c\u0438, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043e\u043d \u0441\u043c\u043e\u0436\u0435\u0442 \u0440\u0430\u0437\u0432\u043e\u0440\u0430\u0447\u0438\u0432\u0430\u0442\u044c\u0441\u044f. \u0424\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438, \u0437\u0430\u0434\u0430\u0447\u0430 \u0441\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043a \u0432\u043e\u043f\u0440\u043e\u0441\u0443 &#171;\u041a\u0430\u043a\u043e\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u0440\u0448\u0438\u043d \u0432 \u0434\u0435\u0440\u0435\u0432\u0435 \u043d\u0443\u0436\u043d\u043e \u043e\u0442\u0440\u0430\u0432\u0438\u0442\u044c, \u0447\u0442\u043e\u0431\u044b \u043d\u0435\u043b\u044c\u0437\u044f \u0431\u044b\u043b\u043e \u0434\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0438\u0437 \u043b\u044e\u0431\u043e\u0433\u043e \u043b\u0438\u0441\u0442\u0430 \u0432 \u0434\u0440\u0443\u0433\u043e\u0439 \u043b\u0438\u0441\u0442 \u043d\u0435 \u043f\u0440\u043e\u0439\u0434\u044f \u0447\u0435\u0440\u0435\u0437 \u043e\u0442\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0435?&#187;.<\/p>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e $3$ \u0442\u0438\u043f\u0430 \u0432\u0435\u0440\u0448\u0438\u043d: \u043b\u0438\u0441\u0442, \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0430 \u0438 \u043e\u0431\u044b\u0447\u043d\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430. \u041b\u0438\u0441\u0442\u043e\u043c \u043d\u0430\u0437\u043e\u0432\u0435\u043c \u0432\u0435\u0440\u0448\u0438\u043d\u0443, \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043d\u0435\u0442 \u0434\u0435\u0442\u0435\u0439 (\u0432\u0441\u0435\u0433\u043e $1$ \u0441\u0432\u044f\u0437\u044c \u0441 \u0434\u0440\u0443\u0433\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439). \u041e\u0431\u044b\u0447\u043d\u044b\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b &#8212; \u0442\u0435, \u0443 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0440\u043e\u0432\u043d\u043e $2$ \u0441\u0432\u044f\u0437\u0438 (\u0434\u043b\u044f \u043d\u0430\u0448\u0435\u0433\u043e \u0442\u0435\u0440\u043c\u0438\u0442\u0430 \u044d\u0442\u043e \u043f\u0443\u0442\u0438 \u0432\u043d\u0438\u0437 \u0438\u043b\u0438 \u0432\u0432\u0435\u0440\u0445). \u0420\u0430\u0437\u0432\u0438\u043b\u043a\u043e\u0439 \u043d\u0430\u0437\u043e\u0432\u0435\u043c \u0432\u0435\u0440\u0448\u0438\u043d\u0443, \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 $3$ \u0438\u043b\u0438 \u0431\u043e\u043b\u044c\u0448\u0435 \u0441\u0432\u044f\u0437\u0435\u0439 \u0441 \u0434\u0440\u0443\u0433\u0438\u043c\u0438. \u0411\u0443\u0434\u0435\u043c \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043a\u043e\u0440\u0435\u043d\u044c \u0442\u043e\u0436\u0435 \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u043e\u0439, \u0434\u0430\u0436\u0435 \u0435\u0441\u043b\u0438 \u0443 \u043d\u0435\u0433\u043e \u0432\u0441\u0435\u0433\u043e $2$ \u0441\u0432\u044f\u0437\u0438, \u0438\u043b\u0438 \u043b\u0438\u0441\u0442\u043e\u043c, \u0435\u0441\u043b\u0438 \u043e\u0434\u043d\u0430. \u0427\u0435\u0440\u0435\u0437 \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0438 \u043c\u043e\u0436\u043d\u043e \u0445\u043e\u0434\u0438\u0442\u044c \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u043b\u0438\u0441\u0442\u0430 \u0432 \u0434\u0440\u0443\u0433\u043e\u0439, \u043b\u0438\u0431\u043e &#171;\u0432\u0432\u0435\u0440\u0445&#187; &#8212; \u0432 \u0441\u0442\u043e\u0440\u043e\u043d\u0443 \u043a\u043e\u0440\u043d\u044f.<\/p>\n<div id=\"attachment_30918\" style=\"width: 522px\" class=\"wp-caption aligncenter\"><a href=\"http:\/\/cpp.mazurok.com\/wp-content\/uploads\/2019\/12\/graphviz1.svg\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-30918\" class=\"wp-image-30918\" role=\"img\" src=\"http:\/\/cpp.mazurok.com\/wp-content\/uploads\/2019\/12\/graphviz1.svg\" alt=\"\u0422\u0438\u043f\u044b \u0432\u0435\u0440\u0448\u0438\u043d\" width=\"512\" height=\"467\" \/><\/a><p id=\"caption-attachment-30918\" class=\"wp-caption-text\">$1$ &#8212; \u043a\u043e\u0440\u0435\u043d\u044c; $5,6,3$ &#8212; \u043b\u0438\u0441\u0442\u044c\u044f; $4$ &#8212; \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0430; $2$ &#8212; \u043e\u0431\u044b\u0447\u043d\u0430\u044f;<\/p><\/div>\n<h2>\u041f\u0435\u0440\u0432\u044b\u0439 \u044d\u0442\u0430\u043f<\/h2>\n<p>\u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0432\u044b\u0433\u043e\u0434\u043d\u0435\u0435 \u0432\u0441\u0435\u0433\u043e &#171;\u0437\u0430\u043a\u0440\u044b\u0432\u0430\u0442\u044c&#187; \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0438. \u0410 \u0441\u0440\u0435\u0434\u0438 \u043d\u0438\u0445 &#8212; \u0442\u0435, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u0435\u0434\u0438\u043d\u044f\u044e\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043b\u0438\u0441\u0442\u043e\u0432 \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e. \u041f\u0443\u0441\u0442\u044c \u043a\u0430\u0436\u0434\u044b\u0439 \u043b\u0438\u0441\u0442 \u043e\u0442\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442 &#171;\u0437\u0430\u043f\u0440\u043e\u0441&#187; \u0432\u0432\u0435\u0440\u0445 \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443 \u043d\u0430 \u0437\u0430\u043a\u0440\u044b\u0442\u0438\u0435 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0439 \u043a \u043d\u0435\u043c\u0443 \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0438. \u041a\u043e\u0433\u0434\u0430 &#171;\u0437\u0430\u043f\u0440\u043e\u0441&#187; \u0434\u043e\u0445\u043e\u0434\u0438\u0442 \u0434\u043e \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0438, \u043e\u043d \u0442\u0443\u0442 \u0436\u0435 \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0435\u0451 \u0441\u0447\u0451\u0442. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0432 \u0434\u0435\u0440\u0435\u0432\u0435 \u0432\u044b\u0448\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u0430 $4$ \u0431\u0443\u0434\u0435\u0442 \u0438\u043c\u0435\u0442\u044c $2$ \u0437\u0430\u043f\u0440\u043e\u0441\u0430 &#8212; \u043e\u0442 \u043b\u0438\u0441\u0442\u043e\u0432 $5$ \u0438 $6$, \u0430 \u043a\u043e\u0440\u0435\u043d\u044c &#8212; $1$ \u0437\u0430\u043f\u0440\u043e\u0441 \u043e\u0442 \u043b\u0438\u0441\u0442\u0430 $3$.<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c, \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u0447\u0438\u0442\u0430\u0435\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u0440\u0448\u0438\u043d \u0441 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432 $\\geqslant2$ \u0438 &#171;\u0437\u0430\u043a\u0440\u044b\u0432\u0430\u0435\u043c&#187; \u0438\u0445.<\/p>\n<h2>\u0412\u0442\u043e\u0440\u043e\u0439 \u044d\u0442\u0430\u043f<\/h2>\n<p>\u0423\u0432\u044b, \u043f\u0435\u0440\u0432\u044b\u0439 \u044d\u0442\u0430\u043f \u043d\u0435 \u0438\u0434\u0435\u0430\u043b\u0435\u043d \u0438 \u043c\u043e\u0436\u0435\u0442 &#171;\u043d\u0435 \u0434\u043e\u043d\u0435\u0441\u0442\u0438&#187; \u0437\u0430\u043f\u0440\u043e\u0441\u044b \u0432 \u043d\u0443\u0436\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e, \u0442.\u043a. \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0438 (\u0430 \u0438\u043c\u0435\u043d\u043d\u043e &#8212; \u0441\u043e\u0435\u0434\u0438\u043d\u044f\u044e\u0449\u0438\u0435 \u043b\u0438\u0441\u0442 \u0438 \u0434\u0440\u0443\u0433\u0443\u044e \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0443) \u043c\u043e\u0433\u0443\u0442 \u043e\u0441\u0442\u0430\u0442\u044c\u0441\u044f \u0441 \u043e\u0434\u043d\u0438\u043c \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u043c \u0438 \u043d\u0435 \u0431\u044b\u0442\u044c \u0437\u0430\u043a\u0440\u044b\u0442\u044b\u043c\u0438. \u0415\u0441\u043b\u0438 \u0442\u0430\u043a\u0438\u0445 \u043c\u043d\u043e\u0433\u043e, \u0442\u0435\u0440\u043c\u0438\u0442 \u0432\u0441\u0435 \u0435\u0449\u0435 \u043c\u043e\u0436\u0435\u0442 \u0445\u043e\u0434\u0438\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u043b\u0438\u0441\u0442\u0430\u043c\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432 \u0442\u0430\u043a\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0435:<\/p>\n<div id=\"attachment_30923\" style=\"width: 1034px\" class=\"wp-caption aligncenter\"><a href=\"http:\/\/cpp.mazurok.com\/wp-content\/uploads\/2019\/12\/graph2.svg\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-30923\" class=\"wp-image-30923 size-large\" role=\"img\" src=\"http:\/\/cpp.mazurok.com\/wp-content\/uploads\/2019\/12\/graph2.svg\" alt=\"\u0414\u0435\u0440\u0435\u0432\u043e 2\" width=\"1024\" height=\"1024\" \/><\/a><p id=\"caption-attachment-30923\" class=\"wp-caption-text\">\u0414\u0435\u0440\u0435\u0432\u043e, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c \u0432\u0442\u043e\u0440\u043e\u0439 \u044d\u0442\u0430\u043f<\/p><\/div>\n<p>\u0412\u0435\u0440\u0448\u0438\u043d\u0430 $2$ \u0438 \u043a\u043e\u0440\u0435\u043d\u044c \u043f\u043e\u043b\u0443\u0447\u0430\u044e\u0442 \u043f\u043e $1$ \u0437\u0430\u043f\u0440\u043e\u0441\u0443 \u0438 \u043e\u0441\u0442\u0430\u044e\u0442\u0441\u044f \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c\u0438, \u0430 \u0443 \u0442\u0435\u0440\u043c\u0438\u0442\u0430 \u043e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u043f\u0443\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u043b\u0438\u0441\u0442\u0430\u043c\u0438 $10$ \u0438 $6$.<\/p>\n<p>\u0414\u043b\u044f \u043f\u0440\u0435\u0434\u043e\u0442\u0432\u0440\u0430\u0449\u0435\u043d\u0438\u044f \u0442\u0430\u043a\u0438\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432, \u043f\u0440\u043e\u0431\u0435\u0436\u0438\u043c\u0441\u044f \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443 &#171;\u0441\u043d\u0438\u0437\u0443 \u0432\u0432\u0435\u0440\u0445&#187; &#8212; \u043e\u0442 \u0441\u0430\u043c\u043e\u0433\u043e \u043d\u0438\u0436\u043d\u0435\u0433\u043e \u0443\u0440\u043e\u0432\u043d\u044f \u0434\u043e \u0432\u0435\u0440\u0445\u043d\u0435\u0433\u043e \u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0438, \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0440\u043e\u0432\u043d\u043e $1$ \u0437\u0430\u043f\u0440\u043e\u0441, \u0441\u043c\u0435\u0441\u0442\u0438\u043c \u0435\u0433\u043e \u0432\u0432\u0435\u0440\u0445 \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u043f\u0435\u0440\u0432\u043e\u043c\u0443 \u044d\u0442\u0430\u043f\u0443 &#8212; \u0434\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0439 \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0438. \u0411\u0443\u0434\u0435\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u044d\u0442\u043e\u0442 \u0448\u0430\u0433, \u043f\u043e\u043a\u0430 \u0435\u0441\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b (\u0441 $1$ \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u043c).<\/p>\n<p>\u0412 \u0438\u0442\u043e\u0433\u0435, \u0432\u0441\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u044b &#171;\u0441\u043e\u0435\u0434\u0438\u043d\u044f\u0442\u0441\u044f&#187; \u0432 \u043d\u0443\u0436\u043d\u044b\u0445 \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0430\u0445, \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0432 \u043d\u0438\u0445 \u0441\u0442\u0430\u043d\u0435\u0442 $\\geqslant2$ \u0438 \u044d\u0442\u0438 \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0438 \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0442\u043e\u0436\u0435 \u0437\u0430\u043a\u0440\u044b\u0442\u044c. \u0414\u043b\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0432\u044b\u0448\u0435, \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u043a\u0440\u044b\u0442 \u043a\u043e\u0440\u0435\u043d\u044c.<\/p>\n<p>\u041e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043a\u043e\u043b-\u0432\u043e \u0437\u0430\u043a\u0440\u044b\u0442\u044b\u0445.<\/p>\n<h1>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430<\/h1>\n<p>\u0414\u0435\u0440\u0435\u0432\u043e \u0431\u0443\u0434\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 <span class=\"lang:java decode:true crayon-inline \">ArrayList&lt;ArrayList&lt;Integer&gt;&gt; tree<\/span>\u00a0. \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432 \u0434\u043b\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u044b $i$ \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0432 <code>killed.get(i)<\/code>. \u0421\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 <code>ArrayList<\/code> <code>used<\/code> \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u0438 <code>dist<\/code>&#8212; <code>ArrayList<\/code> \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0434\u043e \u0432\u0435\u0440\u0448\u0438\u043d, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438 \u0431\u0443\u0434\u0443\u0442 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c\u0441\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e BFS.<\/p>\n<p>\u0424\u0443\u043d\u043a\u0446\u0438\u044f <code>kills<\/code> \u043f\u0440\u0435\u0434\u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0430 \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0434\u043e\u043d\u0435\u0441\u0442\u0438 \u0437\u0430\u043f\u0440\u043e\u0441 \u043e\u0442 \u043b\u0438\u0441\u0442\u0430 \u0434\u043e \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0438. \u041e\u043d\u0430 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442 $3$ \u0441\u043b\u0443\u0447\u0430\u044f:<\/p>\n<ol>\n<li>\u00a0<code>v == p<\/code> &#8212; \u0442\u0435\u043a\u0443\u0449\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0442\u043e\u0439, \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043f\u0440\u0438\u0448\u043b\u0438. \u042d\u0442\u043e \u043a\u0440\u0430\u0439\u043d\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439, \u0433\u043e\u0432\u043e\u0440\u044f\u0449\u0438\u0439 \u043e \u0442\u043e\u043c, \u0447\u0442\u043e \u043c\u044b \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430\u0447\u0430\u043b\u0438 \u0438 \u043d\u0430\u0445\u043e\u0434\u0438\u043c\u0441\u044f \u0432 \u043b\u0438\u0441\u0442\u0435. \u0422\u043e\u0433\u0434\u0430, \u0438\u0434\u0435\u043c \u0432 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438 &#8212; <code>tree.get(v).get(0)<\/code>.<\/li>\n<li><code>tree.get(v).size() == 2<\/code> &#8212; \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u043e\u0431\u044b\u0447\u043d\u043e\u0433\u043e \u0442\u0438\u043f\u0430, \u043f\u0440\u043e\u0441\u0442\u043e \u0438\u0434\u0435\u043c &#171;\u0432\u0432\u0435\u0440\u0445&#187;, \u0432\u044b\u0431\u0438\u0440\u0430\u044f \u0438\u0437 \u0434\u0432\u0443\u0445 \u043f\u0443\u0442\u0435\u0439 \u0442\u043e\u0442, \u0447\u0442\u043e \u043d\u0435 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439.<\/li>\n<li><span class=\"lang:java decode:true crayon-inline \">tree.get(v).size() &gt;= 3<\/span>\u00a0&#8212; \u043f\u043e\u043f\u0430\u043b\u0438 \u0432 \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0443. \u0423\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c \u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 <code>killed.get(v)<\/code> \u0438 \u0432\u044b\u0445\u043e\u0434\u0438\u043c \u0438\u0437 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438.<\/li>\n<\/ol>\n<p>\u0424\u0443\u043d\u043a\u0446\u0438\u044f <code>goup<\/code> \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 <code>kills<\/code> \u043b\u0438\u0448\u044c \u0442\u0435\u043c, \u0447\u0442\u043e \u043f\u0440\u0438 <code>v == p<\/code> \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442 \u0438\u0437 \u0432\u0441\u0435\u0445 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u0442\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0431\u043b\u0438\u0436\u0435 \u043a \u043a\u043e\u0440\u043d\u044e, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f <code>dist<\/code>.<\/p>\n<h2>\u041f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043a\u0430<\/h2>\n<p>\u041c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0438\u0437 $5$ \u0438\u043b\u0438 \u043c\u0435\u043d\u0435\u0435 \u0432\u0435\u0440\u0448\u0438\u043d \u043e\u0442\u0432\u0435\u0442 \u0431\u0443\u0434\u0435\u0442 $1$. \u041f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u044d\u0442\u043e \u0441\u0440\u0430\u0437\u0443 \u043f\u0440\u0438 \u0432\u0432\u043e\u0434\u0435 <code>n<\/code>. \u0414\u0430\u043b\u0435\u0435, \u043e\u0441\u0442\u043e\u0440\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u043c \u0434\u0435\u0440\u0435\u0432\u043e \u0432 <code>tree<\/code> (\u0441\u043c. \u0412\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435). \u0412 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c \u0446\u0438\u043a\u043b\u0435, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c \u043b\u0438\u0441\u0442\u044c\u044f \u0438 \u0437\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u0435\u043c \u0438\u0445 \u0432 <code>ArrayList<\/code> <code>leaves<\/code>. \u041d\u0443\u0436\u043d\u043e \u0443\u0447\u0435\u0441\u0442\u044c \u0442\u043e, \u0447\u0442\u043e \u043a\u043e\u0440\u0435\u043d\u044c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043b\u0438\u0441\u0442\u043e\u043c, \u0435\u0441\u043b\u0438 \u0443 \u043d\u0435\u0433\u043e \u0432\u0441\u0435\u0433\u043e $2$ \u0441\u0432\u044f\u0437\u0438 &#8212; \u043e\u0434\u043d\u0430 \u0441 \u0434\u0435\u0440\u0435\u0432\u043e\u043c, \u0430 \u0434\u0440\u0443\u0433\u0430\u044f &#8212; \u0438\u0441\u043a\u0443\u0441\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0441\u043e\u0437\u0434\u0430\u043d\u043d\u0430\u044f \u043d\u0430\u043c\u0438 \u0432 $0$ \u0432\u0435\u0440\u0448\u0438\u043d\u0443.\u00a0 \u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0448\u0430\u0433 &#8212; \u0437\u0430\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u043f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u0438\u0437 \u043a\u043e\u0440\u043d\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0437\u0430\u043f\u043e\u043b\u043d\u0438\u0442 <code>ArrayList<\/code> <code>dist<\/code> \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f\u043c\u0438 \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0434\u043e \u0432\u0435\u0440\u0448\u0438\u043d.<\/p>\n<h2>\u041f\u0435\u0440\u0432\u044b\u0439 \u044d\u0442\u0430\u043f<\/h2>\n<p>\u041f\u0440\u043e\u0441\u0442\u043e \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c <code>kills (l, l)<\/code> \u0438\u0437 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043b\u0438\u0441\u0442\u0430 <code>l<\/code> \u0434\u043b\u044f &#171;\u043e\u0442\u043f\u0440\u0430\u0432\u043a\u0438&#187; \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432 \u0432 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435 \u0440\u0430\u0437\u0432\u0438\u043b\u043a\u0438.<\/p>\n<h2>\u0412\u0442\u043e\u0440\u043e\u0439 \u044d\u0442\u0430\u043f<\/h2>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e &#171;\u0433\u043b\u0443\u0431\u0438\u043d\u0443&#187; \u0434\u0435\u0440\u0435\u0432\u0430 &#8212; \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043e\u0442 \u043a\u043e\u0440\u043d\u044f. \u0414\u0430\u043b\u0435\u0435, \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0440\u043e\u0432\u043d\u044f \u043e\u0442 \u0441\u0430\u043c\u043e\u0433\u043e \u043d\u0438\u0436\u043d\u0435\u0433\u043e \u0434\u043e \u043a\u043e\u0440\u043d\u044f, \u043f\u0440\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0438 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0441\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c <code>killed.get(i) == 1<\/code> \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c <code>goup (i, i)<\/code>, \u0430 \u0432 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 <code>wentup<\/code> \u0441\u0447\u0438\u0442\u0430\u0435\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0442\u0430\u043a\u0438\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432. \u041a\u0430\u043a \u0442\u043e\u043b\u044c\u043a\u043e \u0438\u0445 \u043d\u0435 \u043e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f &#8212; <code>while<\/code> \u0432\u044b\u0439\u0434\u0435\u0442 \u0438\u0437 \u0446\u0438\u043a\u043b\u0430.<\/p>\n<p>\u041d\u0430\u043a\u043e\u043d\u0435\u0446, \u043e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u0440\u0448\u0438\u043d, \u0443 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 <span class=\"lang:java decode:true crayon-inline\">killed.get(i) &gt;= 2<\/span>.<br \/>\n<a href=\"https:\/\/www.e-olymp.com\/ru\/problems\/9414\">\u0417\u0430\u0434\u0430\u0447\u0430 \u043d\u0430 e-olymp<\/a><br \/>\n<a href=\"https:\/\/ideone.com\/eW82L0\">\u041a\u043e\u0434 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043d\u0430 ideone<\/a><br \/>\n<a href=\"https:\/\/www.e-olymp.com\/ru\/submissions\/7373286\">\u0417\u0430\u0441\u0447\u0438\u0442\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430 e-olymp<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u0423\u0441\u043b\u043e\u0432\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u041d\u0430 \u0434\u0435\u0440\u0435\u0432\u0435 \u0436\u0438\u0432\u0443\u0442 \u0442\u0435\u0440\u043c\u0438\u0442\u044b. \u0412\u0430\u0448\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u0443\u0431\u0438\u0442\u044c \u0438\u0445 \u0432\u0441\u0435\u0445. \u0414\u0435\u0440\u0435\u0432\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u0441\u0432\u044f\u0437\u043d\u044b\u043c \u0433\u0440\u0430\u0444\u043e\u043c \u0441 $n$ \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438 \u0438 $n &#8212; 1$ \u0440\u0435\u0431\u0440\u0430\u043c\u0438. \u0427\u0442\u043e\u0431\u044b \u0443\u0431\u0438\u0442\u044c \u0442\u0435\u0440\u043c\u0438\u0442\u043e\u0432, \u0412\u0430\u043c \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u043e\u0442\u0440\u0430\u0432\u0438\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b. \u0415\u0441\u043b\u0438 \u0442\u0435\u0440\u043c\u0438\u0442 \u043f\u043e\u043f\u0430\u0434\u0430\u0435\u0442 \u043d\u0430 \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0441 \u044f\u0434\u043e\u043c, \u0442\u043e \u043e\u043d \u043d\u0435\u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e \u0443\u043c\u0438\u0440\u0430\u0435\u0442. \u0412\u044b \u043d\u0435 \u0437\u043d\u0430\u0435\u0442\u0435, \u0433\u0434\u0435 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0442\u0435\u0440\u043c\u0438\u0442\u044b. \u041d\u043e \u0412\u044b \u0437\u043d\u0430\u0435\u0442\u0435, \u0447\u0442\u043e \u0442\u0435\u0440\u043c\u0438\u0442\u044b &hellip; <a href=\"https:\/\/java.mazurok.com\/?p=5245\" class=\"more-link\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":145,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[109],"tags":[735,279,63,180,565],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/5245"}],"collection":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/users\/145"}],"replies":[{"embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5245"}],"version-history":[{"count":23,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/5245\/revisions"}],"predecessor-version":[{"id":5268,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/5245\/revisions\/5268"}],"wp:attachment":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5245"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5245"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5245"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}