結果

問題 No.386 貪欲な領主
ユーザー uafr_csuafr_cs
提出日時 2016-07-02 00:03:09
言語 Java21
(openjdk 21)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,666 bytes
コンパイル時間 2,549 ms
コンパイル使用メモリ 80,224 KB
実行使用メモリ 294,884 KB
最終ジャッジ日時 2024-10-12 19:15:38
合計ジャッジ時間 9,649 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 53 ms
37,076 KB
testcase_01 AC 51 ms
37,036 KB
testcase_02 AC 55 ms
36,868 KB
testcase_03 AC 53 ms
36,828 KB
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 AC 155 ms
43,100 KB
testcase_08 AC 546 ms
67,856 KB
testcase_09 AC 190 ms
48,724 KB
testcase_10 AC 52 ms
37,156 KB
testcase_11 AC 52 ms
37,232 KB
testcase_12 AC 143 ms
42,768 KB
testcase_13 AC 215 ms
45,972 KB
testcase_14 TLE -
testcase_15 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.StringTokenizer;

public class Main {
	
	public static class UnionFind{
		int[] par; //
		
		public UnionFind(int n){
			par = new int[n];
			for(int i = 0; i < n; i++){ par[i] = -1; }
		}
		
		public int find(int x){
			if(par[x] < 0){
				return x;
			}else{
				return par[x] = find(par[x]);
			}
		}
		
		public boolean union(int x, int y){
			x = find(x);
			y = find(y);
			
			if(x != y){
				if(par[y] < par[x]) {  // 多い方が根になるようにスワップする.
					int tmp = x; x = y; y = tmp;
				}
				par[x] += par[y];
				par[y] = x;
				return true;
			}else{
				return false;
			}
		}
		
		public boolean same(int x, int y){
			return find(x) == find(y);
		}
		
		public int size(int x){
			return -par[find(x)];
		}
	}
	
	// DFS で 前順走査(preorder) で 一番近い親を探す. 部分木のマージに, UnionFind を使う .
	public static void dfs(ArrayList<HashMap<Integer, HashSet<Integer>>> querys, int[] lcas, int node, int parent, boolean[] visited, int[] ancestor, ArrayList<HashSet<Integer>> adj, UnionFind uf) {
		ancestor[uf.find(node)] = node; // 自分の祖先は自分.
		
		for (final int next : adj.get(node)){
			if(next == parent){ continue; }
			
			dfs(querys, lcas, next, node, visited, ancestor, adj, uf);
			uf.union(node, next); // next以下のLCAを探索し終えたので, 部分木を併合.
			ancestor[uf.find(node)] = node; // 併合した祖先は自分(部分木内はもう終えてる)
		}

		visited[node] = true;
		for(final Entry<Integer, HashSet<Integer>> pair_entry : querys.get(node).entrySet()){
			final int pair_node = pair_entry.getKey();
			
			for(final int pair_index : pair_entry.getValue()){
				if(visited[pair_node]){
					lcas[pair_index] = ancestor[uf.find(pair_node)];
				}
			}
		}
	}

	public static int[] offlineLCA(int[] us, int[] vs, ArrayList<HashSet<Integer>> adj) {
		final int n = adj.size();
		int[] lca_nodes = new int[us.length], ancestor = new int[n + 1];
		boolean[] visited = new boolean[n + 1];
		UnionFind uf = new UnionFind(n + 1);
		
		ArrayList<HashMap<Integer, HashSet<Integer>>> querys = new ArrayList<HashMap<Integer, HashSet<Integer>>>();
		for(int i = 0; i < n; i++){
			querys.add(new HashMap<Integer, HashSet<Integer>>());
		}
		
		for(int i = 0; i < us.length; i++){
			if(!querys.get(us[i]).containsKey(vs[i])){
				querys.get(us[i]).put(vs[i], new HashSet<Integer>());
			}
			querys.get(us[i]).get(vs[i]).add(i);
			
			if(!querys.get(vs[i]).containsKey(us[i])){
				querys.get(vs[i]).put(us[i], new HashSet<Integer>());
			}
			querys.get(vs[i]).get(us[i]).add(i);
		}
		
		dfs(querys, lca_nodes, 0, -1, visited, ancestor, adj, uf);
		return lca_nodes;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		final int N = sc.nextInt();
		ArrayList<HashSet<Integer>> tree = new ArrayList<HashSet<Integer>>();
		for(int i = 0; i < N; i++){
			tree.add(new HashSet<Integer>());
		}
		
		for(int i = 0; i < N - 1; i++){
			final int A = sc.nextInt();
			final int B = sc.nextInt();
			
			tree.get(A).add(B);
			tree.get(B).add(A);
		}
		
		long[] node_costs = new long[N];
		for(int i = 0; i < N; i++){
			node_costs[i] = sc.nextLong();
		}
		
		long[] from_0_cost = new long[N];
		LinkedList<Integer> node_queue = new LinkedList<Integer>();
		LinkedList<Integer> parent_queue = new LinkedList<Integer>();
		node_queue.add(0);
		parent_queue.add(-1);
		while(!node_queue.isEmpty()){
			final int node = node_queue.poll();
			final int parent = parent_queue.poll();
			
			if(parent >= 0){
				from_0_cost[node] += from_0_cost[parent];
			}
			from_0_cost[node] += node_costs[node];
			
			for(final int next : tree.get(node)){
				if(next == parent){ continue; }
				if(next == node){ continue; }
				
				node_queue.add(next);
				parent_queue.add(node);
			}
		}
		
		final int M = sc.nextInt();
		int[] as = new int[M];
		int[] bs = new int[M];
		long[] cs = new long[M];

		for (int i = 0; i < M; i++) {
			final int A = sc.nextInt();
			final int B = sc.nextInt();
			final int C = sc.nextInt();
			
			as[i] = A; bs[i] = B; cs[i] = C;
		}
		
		int[] lcas = offlineLCA(as, bs, tree);
		
		long sum = 0;
		for(int i = 0; i < M; i++){
			final long A_cost = from_0_cost[as[i]];
			final long B_cost = from_0_cost[bs[i]];
			final long lca_cost = from_0_cost[lcas[i]];
			final long lca_node_cost = node_costs[lcas[i]];
			//System.out.println(A_cost + " " + B_cost + " " + lca_cost + " " +  lca_node_cost);
			//System.out.println(cs[i] * (A_cost + B_cost - 2 * lca_cost + lca_node_cost));
			
			sum += cs[i] * (A_cost + B_cost - 2 * lca_cost + lca_node_cost);
		}
		System.out.println(sum);
	}
	
	public static class Scanner implements AutoCloseable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() {
			try {
				while (!hasNext()) {tok = new StringTokenizer(br.readLine());}
			} catch(IOException e){ /* ignore */ }
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() {
			getLine(); return tok.nextToken();
		}

		public int nextInt(){
			return Integer.parseInt(next());
		}
		
		public long nextLong(){
			return Long.parseLong(next());
		}
		
		public void close() {
			try{ br.close(); } catch (IOException e){ /*ignore*/ }
		}
	}
}
0