#100912 (Java) No.386 貪欲な領主

• 問題: No.386 貪欲な領主
• ユーザー: uafr_cs
• 提出日時: 2016-07-01 23:28:11
• 言語: Java (openjdk 23)
• 結果: TLE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 5,620 bytes
• コンパイル時間: 2,380 ms
• コンパイル使用メモリ: 80,336 KB
• 実行使用メモリ: 286,780 KB
• 最終ジャッジ日時: 2024-10-12 19:07:00
• 合計ジャッジ時間: 17,641 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

ファイルパターン	結果
other	AC * 11 TLE * 5

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
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];
        boolean[] visited = new boolean[n];
        UnionFind uf = new UnionFind(n);
        
        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; }
                
                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*/ }
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX