Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedWriter;
- import java.io.DataInputStream;
- import java.io.IOException;
- import java.io.OutputStreamWriter;
- import java.io.PrintWriter;
- import java.util.ArrayList;
- import java.util.Arrays;
- public class dmopc18c4p5 {
- static class Edge {
- int ev, cost, uses, used, initial;
- public Edge(int ev, int cost, int uses, int used, int initial) {
- this.ev = ev;
- this.cost = cost;
- this.uses = uses;
- this.used = used;
- this.initial = initial;
- }
- }
- static ArrayList<Edge>[] a;
- static int max, start;
- static int[] vis;
- static boolean[] vis1;
- @SuppressWarnings("unchecked")
- public static void main(String[] args) throws IOException {
- int n = readInt(), k = readInt();
- a = new ArrayList[n + 1];
- vis = new int[n + 1];
- Arrays.fill(vis, 1);
- for (int i = 0; i < n + 1; i++) {
- a[i] = new ArrayList<Edge>();
- }
- for (int i = 0; i < k; i++) {
- int x = readInt();
- vis[x - 1] = 2;
- }
- for (int i = 0; i < n - 1; i++) {
- int c1 = readInt(), c2 = readInt(), cost = readInt();
- if (vis[i] == 2) {
- a[c1].add(new Edge(c2, cost, 2, 0, 2));
- a[c2].add(new Edge(c1, cost, 2, 0, 2));
- } else {
- a[c1].add(new Edge(c2, cost, 1, 0, 1));
- a[c2].add(new Edge(c1, cost, 1, 0, 1));
- }
- }
- vis1 = new boolean[n + 1];
- max = 0;
- for (int i = 1; i <= n; i++) {
- longest(i, 0);
- }
- System.out.println(max);
- }
- public static int longest(int x, int d) {
- // System.out.println(x + " " + d);
- if (d > max) {
- max = d;
- }
- for (Edge e : a[x]) {
- if (e.used < e.uses) {
- e.used++;
- for (Edge v : a[e.ev]) {
- if (v.ev == x) {
- v.used++;
- }
- }
- longest(e.ev, d + e.cost);
- e.used--;
- for (Edge v : a[e.ev]) {
- if (v.ev == x) {
- v.used--;
- }
- }
- }
- }
- return max;
- }
- final private static int BUFFER_SIZE = 1 << 16;
- private static DataInputStream din = new DataInputStream(System.in);
- private static byte[] buffer = new byte[BUFFER_SIZE];
- private static int bufferPointer = 0, bytesRead = 0;
- static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
- public static String readLine() throws IOException {
- byte[] buf = new byte[1000000]; // line length
- int cnt = 0, c;
- while ((c = Read()) != -1) {
- if (c == '\n')
- break;
- buf[cnt++] = (byte) c;
- }
- return new String(buf, 0, cnt);
- }
- public static String read() throws IOException {
- byte[] ret = new byte[1024];
- int idx = 0;
- byte c = Read();
- while (c <= ' ') {
- c = Read();
- }
- do {
- ret[idx++] = c;
- c = Read();
- } while (c != -1 && c != ' ' && c != '\n' && c != '\r');
- return new String(ret, 0, idx);
- }
- public static int readInt() throws IOException {
- int ret = 0;
- byte c = Read();
- while (c <= ' ')
- c = Read();
- boolean neg = (c == '-');
- if (neg)
- c = Read();
- do {
- ret = ret * 10 + c - '0';
- } while ((c = Read()) >= '0' && c <= '9');
- if (neg)
- return -ret;
- return ret;
- }
- public static long readLong() throws IOException {
- long ret = 0;
- byte c = Read();
- while (c <= ' ')
- c = Read();
- boolean neg = (c == '-');
- if (neg)
- c = Read();
- do {
- ret = ret * 10 + c - '0';
- } while ((c = Read()) >= '0' && c <= '9');
- if (neg)
- return -ret;
- return ret;
- }
- public static double readDouble() throws IOException {
- double ret = 0, div = 1;
- byte c = Read();
- while (c <= ' ')
- c = Read();
- boolean neg = (c == '-');
- if (neg)
- c = Read();
- do {
- ret = ret * 10 + c - '0';
- } while ((c = Read()) >= '0' && c <= '9');
- if (c == '.') {
- while ((c = Read()) >= '0' && c <= '9') {
- ret += (c - '0') / (div *= 10);
- }
- }
- if (neg)
- return -ret;
- return ret;
- }
- private static void fillBuffer() throws IOException {
- bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
- if (bytesRead == -1)
- buffer[0] = -1;
- }
- private static byte Read() throws IOException {
- if (bufferPointer == bytesRead)
- fillBuffer();
- return buffer[bufferPointer++];
- }
- public void close() throws IOException {
- if (din == null)
- return;
- din.close();
- }
- static void print(Object o) {
- pr.print(o);
- }
- static void println(Object o) {
- pr.println(o);
- }
- static void flush() {
- pr.flush();
- }
- static void println() {
- pr.println();
- }
- static void exit() throws IOException {
- din.close();
- pr.close();
- System.exit(0);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement