結果
| 問題 |
No.898 tri-βutree
|
| コンテスト | |
| ユーザー |
 Oland
|
| 提出日時 | 2020-05-21 19:20:59 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 874 ms / 4,000 ms |
| コード長 | 10,659 bytes |
| コンパイル時間 | 3,868 ms |
| コンパイル使用メモリ | 81,620 KB |
| 実行使用メモリ | 97,300 KB |
| 最終ジャッジ日時 | 2024-11-08 23:43:59 |
| 合計ジャッジ時間 | 20,700 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 21 |
ソースコード
import java.io.*;
import java.util.*;
@SuppressWarnings("unused")
public class Main {
FastScanner in;
PrintWriter out;
final static int MOD = (int)1e9+7;
void solve(){
int N = in.nextInt();
ArrayList<ArrayList<Edge>> g = new ArrayList<>();
for(int i = 0; i < N; i++) g.add(new ArrayList<>());
for(int i = 0; i < N - 1; i++){
int u = in.nextInt(), v = in.nextInt();
long cost = in.nextLong();
g.get(u).add(new Edge(u, v, cost));
g.get(v).add(new Edge(v, u, cost));
}
long[] sum = new long[N];
boolean[] visited = new boolean[N];
ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
visited[0] = true;
queue.addLast(0);
while(!queue.isEmpty()){
int v = queue.removeFirst();
for(Edge edge : g.get(v)){
int to = edge.to;
long cost = edge.cost;
if(visited[to]) continue;
visited[to] = true;
sum[to] = sum[v] + cost;
queue.addLast(to);
}
}
LowestCommonAncestor lca = new LowestCommonAncestor(g, 0);
int Q = in.nextInt();
for(int i = 0; i < Q; i++){
int x = in.nextInt(), y = in.nextInt(), z = in.nextInt();
long ans = 0;
ans += sum[x] + sum[y] - 2 * sum[lca.getLCA(x, y)];
ans += sum[y] + sum[z] - 2 * sum[lca.getLCA(y, z)];
ans += sum[z] + sum[x] - 2 * sum[lca.getLCA(z, x)];
ans /= 2;
out.println(ans);
}
}
class Edge implements Comparable<Edge>{
int from;
int to;
long cost;
public Edge(int f, int t, long c){
from = f; to = t; cost = c;
}
@Override
public int compareTo(Edge o) {
return Long.compare(this.cost, o.cost);
}
}
class LowestCommonAncestor {
int[] vs, depth, id;
ArrayList<ArrayList<Edge>> T;
SparseTableIndex sti;
//Euler-Tour Technique
public LowestCommonAncestor(ArrayList<ArrayList<Edge>> T, int root){
vs = new int[T.size()*2-1];
depth = new int[T.size()*2-1];
id = new int[T.size()];
this.T = T;
dfsStack(root);
sti = new SparseTableIndex(depth);
}
void dfsStack(int root){
ArrayDeque<int[]> stack = new ArrayDeque<>();
int k = 0;
stack.addLast(new int[]{0, root, -1, 0});
while(!stack.isEmpty()){
int[] node = stack.removeLast();
int v = node[1], p = node[2], d = node[3];
if(node[0] == 0){
id[v] = k;
vs[k] = v;
depth[k] = d;
k++;
for(Edge edge : T.get(v)) {
if (edge.to == p) continue;
stack.addLast(new int[]{1, v, p, d});
stack.addLast(new int[]{0, edge.to, v, d+1});
}
}else{
vs[k] = v;
depth[k] = d;
k++;
}
}
}
public int getLCA(int u, int v){
int L = Math.min(id[u], id[v]), R = Math.max(id[u], id[v]);
return vs[sti.get(L, R+1)];
}
class SparseTableIndex {
int[][] table;
int[] height;
int[] v;
public SparseTableIndex(int[] v){
init(v);
}
void init(int[] v){
this.v = Arrays.copyOf(v, v.length);
int n = v.length, h = 0;
while((1<<h) <= n) h++;
table = new int[h][1<<h];
height = new int[n+1];
for(int i = 2; i <= n; i++) height[i] = height[i>>1]+1;
for(int i = 0; i < n; i++) table[0][i] = i;
for(int i = 1; i < h; i++) {
for (int j = 0; j < n; j++) {
int x = table[i - 1][j], y = table[i - 1][Math.min(j + (1 << (i - 1)), n - 1)];
table[i][j] = v[x] <= v[y] ? x : y;
}
}
}
public int get(int a, int b){
int l = height[b-a];
int x = table[l][a], y = table[l][b-(1<<l)];
return v[x] <= v[y] ? x : y;
}
}
}
public static void main(String[] args) {
new Main().m();
}
private void m() {
in = new FastScanner(System.in);
out = new PrintWriter(System.out);
/*
try {
String path = "input.txt";
out = new PrintWriter(new BufferedWriter(new FileWriter(new File(path))));
}catch (IOException e){
e.printStackTrace();
}
*/
solve();
out.flush();
in.close();
out.close();
}
static class FastScanner {
private Reader input;
public FastScanner() {this(System.in);}
public FastScanner(InputStream stream) {this.input = new BufferedReader(new InputStreamReader(stream));}
public void close() {
try {
this.input.close();
} catch (IOException e) {
e.printStackTrace();
}
}
public int nextInt() {return (int) nextLong();}
public long nextLong() {
try {
int sign = 1;
int b = input.read();
while ((b < '0' || '9' < b) && b != '-' && b != '+') {
b = input.read();
}
if (b == '-') {
sign = -1;
b = input.read();
} else if (b == '+') {
b = input.read();
}
long ret = b - '0';
while (true) {
b = input.read();
if (b < '0' || '9' < b) return ret * sign;
ret *= 10;
ret += b - '0';
}
} catch (IOException e) {
e.printStackTrace();
return -1;
}
}
public double nextDouble() {
try {
double sign = 1;
int b = input.read();
while ((b < '0' || '9' < b) && b != '-' && b != '+') {
b = input.read();
}
if (b == '-') {
sign = -1;
b = input.read();
} else if (b == '+') {
b = input.read();
}
double ret = b - '0';
while (true) {
b = input.read();
if (b < '0' || '9' < b) break;
ret *= 10;
ret += b - '0';
}
if (b != '.') return sign * ret;
double div = 1;
b = input.read();
while ('0' <= b && b <= '9') {
ret *= 10;
ret += b - '0';
div *= 10;
b = input.read();
}
return sign * ret / div;
} catch (IOException e) {
e.printStackTrace();
return Double.NaN;
}
}
public char nextChar() {
try {
int b = input.read();
while (Character.isWhitespace(b)) {
b = input.read();
}
return (char) b;
} catch (IOException e) {
e.printStackTrace();
return 0;
}
}
public String nextStr() {
try {
StringBuilder sb = new StringBuilder();
int b = input.read();
while (Character.isWhitespace(b)) {
b = input.read();
}
while (b != -1 && !Character.isWhitespace(b)) {
sb.append((char) b);
b = input.read();
}
return sb.toString();
} catch (IOException e) {
e.printStackTrace();
return "";
}
}
public String nextLine() {
try {
StringBuilder sb = new StringBuilder();
int b = input.read();
while (b != -1 && b != '\n') {
sb.append((char) b);
b = input.read();
}
return sb.toString();
} catch (IOException e) {
e.printStackTrace();
return "";
}
}
public int[] nextIntArray(int n) {
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt();
}
return res;
}
public int[] nextIntArrayDec(int n) {
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt() - 1;
}
return res;
}
public int[] nextIntArray1Index(int n) {
int[] res = new int[n + 1];
for (int i = 0; i < n; i++) {
res[i + 1] = nextInt();
}
return res;
}
public long[] nextLongArray(int n) {
long[] res = new long[n];
for (int i = 0; i < n; i++) {
res[i] = nextLong();
}
return res;
}
public long[] nextLongArrayDec(int n) {
long[] res = new long[n];
for (int i = 0; i < n; i++) {
res[i] = nextLong() - 1;
}
return res;
}
public long[] nextLongArray1Index(int n) {
long[] res = new long[n + 1];
for (int i = 0; i < n; i++) {
res[i + 1] = nextLong();
}
return res;
}
public double[] nextDoubleArray(int n) {
double[] res = new double[n];
for (int i = 0; i < n; i++) {
res[i] = nextDouble();
}
return res;
}
}
}