結果

問題 No.1030 だんしんぐぱーりない
ユーザー ks2mks2m
提出日時 2020-04-17 22:50:41
言語 Java19
(openjdk 21)
結果
AC  
実行時間 1,856 ms / 2,000 ms
コード長 5,501 bytes
コンパイル時間 4,547 ms
コンパイル使用メモリ 84,536 KB
実行使用メモリ 95,672 KB
最終ジャッジ日時 2023-07-27 01:45:10
合計ジャッジ時間 51,768 ms
ジャッジサーバーID
(参考情報)
judge11 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 52 ms
50,232 KB
testcase_01 AC 51 ms
49,844 KB
testcase_02 AC 53 ms
50,348 KB
testcase_03 AC 51 ms
50,064 KB
testcase_04 AC 52 ms
50,156 KB
testcase_05 AC 1,382 ms
79,492 KB
testcase_06 AC 1,285 ms
78,528 KB
testcase_07 AC 1,013 ms
68,108 KB
testcase_08 AC 984 ms
67,444 KB
testcase_09 AC 1,316 ms
79,592 KB
testcase_10 AC 760 ms
63,528 KB
testcase_11 AC 1,285 ms
69,820 KB
testcase_12 AC 1,227 ms
78,516 KB
testcase_13 AC 1,156 ms
80,944 KB
testcase_14 AC 1,389 ms
75,540 KB
testcase_15 AC 962 ms
66,508 KB
testcase_16 AC 1,252 ms
71,760 KB
testcase_17 AC 1,335 ms
81,076 KB
testcase_18 AC 1,455 ms
74,008 KB
testcase_19 AC 1,035 ms
66,960 KB
testcase_20 AC 1,162 ms
71,728 KB
testcase_21 AC 1,089 ms
70,848 KB
testcase_22 AC 1,134 ms
71,736 KB
testcase_23 AC 1,324 ms
72,808 KB
testcase_24 AC 1,098 ms
68,292 KB
testcase_25 AC 1,182 ms
66,360 KB
testcase_26 AC 924 ms
61,960 KB
testcase_27 AC 1,037 ms
66,420 KB
testcase_28 AC 1,295 ms
77,400 KB
testcase_29 AC 1,112 ms
77,196 KB
testcase_30 AC 1,064 ms
71,808 KB
testcase_31 AC 1,132 ms
68,672 KB
testcase_32 AC 1,343 ms
80,056 KB
testcase_33 AC 1,305 ms
78,572 KB
testcase_34 AC 828 ms
66,436 KB
testcase_35 AC 1,762 ms
91,056 KB
testcase_36 AC 1,790 ms
93,356 KB
testcase_37 AC 1,770 ms
95,332 KB
testcase_38 AC 1,856 ms
94,724 KB
testcase_39 AC 1,772 ms
95,672 KB
testcase_40 AC 54 ms
49,868 KB
testcase_41 AC 51 ms
49,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.BiFunction;

public class Main {
	static int[] c;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int k = Integer.parseInt(sa[1]);
		int q = Integer.parseInt(sa[2]);

		sa = br.readLine().split(" ");
		c = new int[n];
		for (int i = 0; i < n; i++) {
			c[i] = Integer.parseInt(sa[i]);
		}

		sa = br.readLine().split(" ");
		int[] a = new int[k];
		for (int i = 0; i < k; i++) {
			a[i] = Integer.parseInt(sa[i]) - 1;
		}

		List<List<Integer>> list = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			list.add(new ArrayList<>());
		}
		for (int i = 0; i < n - 1; i++) {
			sa = br.readLine().split(" ");
			int e = Integer.parseInt(sa[0]) - 1;
			int f = Integer.parseInt(sa[1]) - 1;
			list.get(e).add(f);
			list.get(f).add(e);
		}
		SegTreeLCA lca = new SegTreeLCA(n, list, 0);
		SegTree<Integer> st = new SegTree<Integer>(k, -1, (o1, o2) -> {
			if (o1 == -1) return o2;
			if (o2 == -1) return o1;
			return lca.lca(o1, o2).i;
		});
		for (int i = 0; i < k; i++) {
			st.update(i, a[i]);
		}

		PrintWriter pw = new PrintWriter(System.out);
		for (int i = 0; i < q; i++) {
			sa = br.readLine().split(" ");
			if (sa[0].equals("1")) {
				int x = Integer.parseInt(sa[1]) - 1;
				int y = Integer.parseInt(sa[2]) - 1;
				st.update(x, y);
			} else {
				int l = Integer.parseInt(sa[1]) - 1;
				int r = Integer.parseInt(sa[2]);
				pw.println(lca.get(st.query(l, r)).c);
			}
		}
		pw.flush();
		br.close();
	}

	static class SegTreeLCA {
		int n = 2;
		int n2, idx;
		Obj[] arr;
		int[] first;
		Obj INF = new Obj(-1, Integer.MAX_VALUE, 0);

		/**
		 * 初期化
		 * @param size 頂点数
		 * @param list 隣接リスト
		 * @param root 根の頂点番号
		 */
		public SegTreeLCA(int size, List<List<Integer>> list, int root) {
			while (n < size) {
				n <<= 1;
			}
			n <<= 1;
			n2 = n * 2 - 1;
			idx = n - 1;
			arr = new Obj[n2];
			first = new int[size];
			Arrays.fill(first, -1);

			Obj r = new Obj(root, 0, c[root]);
			arr[idx] = r;
			first[root] = idx - n + 1;
			idx++;
			dfs(list, r, -1);
			for (int i = idx; i < n2; i++) {
				arr[i] = INF;
			}
			for (int i = n - 2; i >= 0; i--) {
				if (arr[i * 2 + 1].dep < arr[i * 2 + 2].dep) {
					arr[i] = arr[i * 2 + 1];
				} else {
					arr[i] = arr[i * 2 + 2];
				}
			}
		}

		private void dfs(List<List<Integer>> list, Obj cur, int p) {
			for (int ch : list.get(cur.i)) {
				if (ch != p) {
					int cmax = Math.max(cur.c, c[ch]);
					Obj o = new Obj(ch, cur.dep + 1, cmax);
					arr[idx] = o;
					if (first[ch] == -1) {
						first[ch] = idx - n + 1;
					}
					idx++;
					dfs(list, o, cur.i);
					arr[idx] = cur;
					idx++;
				}
			}
		}

		/**
		 * 頂点Iのオブジェクト取得(0≦I<size)
		 */
		public Obj get(int i) {
			return arr[first[i] + n - 1];
		}

		/**
		 * 頂点A,BのLCA取得(0≦A,B<size)
		 */
		public Obj lca(int a, int b) {
			int l = Math.min(first[a], first[b]);
			int r = Math.max(first[a], first[b]);
			return query(l, r + 1, 0, 0, n);
		}
		private Obj query(int l, int r, int k, int beg, int end) {
			if (end <= l || r <= beg) return INF; // 交差しない
			if (l <= beg && end <= r) return arr[k]; // 完全に含む
			Obj o1 = query(l, r, k * 2 + 1, beg, (beg + end) / 2);
			Obj o2 = query(l, r, k * 2 + 2, (beg + end) / 2, end);
			if (o1.dep < o2.dep) {
				return o1;
			}
			return o2;
		}

		private static class Obj {
			int i, dep, c;

			public Obj(int i, int dep, int c) {
				this.i = i;
				this.dep = dep;
				this.c = c;
			}
		}
	}

	static class SegTree<T> {
		// 親へのアクセス:(n - 1) / 2
		// 子へのアクセス:n * 2 + 1、n * 2 + 2
		int n = 2; // 要素(葉)の数
		int n2; // 全ノード数
		T NA;
		List<T> list;
		BiFunction<T, T, T> func;

		/**
		 * 初期化 O(N)
		 * @param num 要素(葉)の数
		 * @param na 無効とみなせる値
		 * @param func 区間に対する操作が可能な関数(戻り値は新規オブジェクト)
		 */
		public SegTree(int num, T na, BiFunction<T, T, T> func) {
			while (n < num) n <<= 1;
			n2 = n * 2 - 1;
			NA = na;
			list = new ArrayList<T>(n2);
			for (int i = 0; i < n2; i++) list.add(NA);
			this.func = func;
		}

		/**
		 * 更新 O(logN)
		 * @param i インデックス(0~n-1)
		 * @param x 更新値
		 */
		void update(int i, T x) {
			i += n - 1; // arr上でのインデックス
			list.set(i, x);
			while (i > 0) {
				i = (i - 1) / 2;
				list.set(i, func.apply(list.get(i * 2 + 1), list.get(i * 2 + 2)));
			}
		}

		/**
		 * 取得 O(logN)
		 * インデックスl以上r未満の区間の値
		 */
		T query(int l, int r) {
			return query(l, r, 0, 0, n);
		}

		/**
		 * 取得 O(logN)
		 * インデックスl以上r未満の区間の値、beg, endにはノードkに対応する区間
		 * query(l, r, 0, 0, n);
		 */
		private T query(int l, int r, int k, int beg, int end) {
			if (end <= l || r <= beg) return NA; // 交差しない
			if (l <= beg && end <= r) return list.get(k); // 完全に含む
			T v1 = query(l, r, k * 2 + 1, beg, (beg + end) / 2);
			T v2 = query(l, r, k * 2 + 2, (beg + end) / 2, end);
			return func.apply(v1, v2);
		}
	}
}
0