fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class TaskE {
  5.     private final InputReader reader;
  6.     private final OutputWriter writer;
  7.  
  8.     public TaskE(InputReader reader, OutputWriter writer) {
  9.         this.reader = reader;
  10.         this.writer = writer;
  11.     }
  12.  
  13.     public static void main(String[] args) {
  14.         InputReader reader = new InputReader(System.in);
  15.         OutputWriter writer = new OutputWriter(System.out);
  16.         new TaskE(reader, writer).run();
  17.         writer.writer.flush();
  18.     }
  19.  
  20.     int[] F;
  21.     class Edge implements Comparable<Edge> {
  22.         int a, b, l;
  23.         Edge(int a, int b, int l) {
  24.             this.a = a;
  25.             this.b = b;
  26.             this.l = l;
  27.         }
  28.         @Override
  29.         public int compareTo(Edge other) {
  30.             return -Integer.compare(this.l, other.l);
  31.         }
  32.     }
  33.  
  34.     List<Integer>[] E;
  35.  
  36.     class Node {
  37.         int l, r, sum;
  38.         boolean whole;
  39.         Node(int v) {
  40.             if (v == 0) {
  41.                 l = r = sum = 0;
  42.                 whole = false;
  43.             } else {
  44.                 l = r = 1;
  45.                 sum = 0;
  46.                 whole = true;
  47.             }
  48.         }
  49.         Node(int l, int r, int sum, boolean whole) {
  50.             this.l = l;
  51.             this.r = r;
  52.             this.sum = sum;
  53.             this.whole = whole;
  54.         }
  55.         Node reverse() {
  56.             return new Node(r, l, sum, whole);
  57.         }
  58.         int value() {
  59.             if (whole)
  60.                 return F[l]; //!
  61.             else
  62.                 return F[l] + F[r] + sum;
  63.         }
  64.     }
  65.  
  66.     Node combine(Node a, Node b) {
  67.         if (a == null)
  68.             return b;
  69.         if (b == null)
  70.             return a;
  71.         if (a.whole && b.whole)
  72.             return new Node(a.l + b.l, a.r + b.r, a.sum + b.sum, true);
  73.         if (a.whole && !b.whole)
  74.             return new Node(a.l + b.l, b.r, a.sum + b.sum, false);
  75.         if (!a.whole && b.whole)
  76.             return new Node(a.l, a.r + b.r, a.sum + b.sum, false);
  77.         return new Node(a.l, b.r, a.sum + b.sum + F[a.r + b.l], false);
  78.     }
  79.  
  80.     class SegmentTree {
  81.         int N;
  82.         Node[] T;
  83.         SegmentTree(int n) {
  84.             N = 1;
  85.             while (N < n)
  86.                  N <<= 1;
  87.             T = new Node[2 * N];
  88.             for (int i = N + n - 1; i >= N; i--)
  89.                 T[i] = new Node(0);
  90.             for (int i = N - 1; i > 0; i--)
  91.                 T[i] = combine(T[2 * i], T[2 * i + 1]);
  92.         }
  93.         void set(int x, int i) {
  94.             x += N;
  95.             T[x] = new Node(i);
  96.             for (x >>= 1; x > 0; x >>= 1)
  97.                 T[x] = combine(T[2 * x], T[2 * x + 1]);
  98.         }
  99.         Node get(int l, int r) {
  100.             Node resl = null, resr = null;
  101.             l += N;
  102.             r += N;
  103.             while (l <= r) {
  104.                 if ((l & 1) == 1)
  105.                     resl = combine(resl, T[l]);
  106.                 if ((r & 1) == 0)
  107.                     resr = combine(T[r], resr);
  108.                 l = (l + 1) >> 1;
  109.                 r = (r - 1) >> 1;
  110.             }
  111.             return combine(resl, resr);
  112.         }
  113.     }
  114.  
  115.     int lgn;
  116.     int[][] up;
  117.     int[] S;
  118.     int[] to;
  119.     int[] D;
  120.     void DFS1(int x, int p) {
  121.         up[0][x] = p;
  122.         for (int d = 1; d < lgn; d++)
  123.             up[d][x] = up[d - 1][up[d - 1][x]];
  124.         S[x] = 1;
  125.         to[x] = -1;
  126.         for (int i = 0; i < E[x].size(); i++) {
  127.             int y = E[x].get(i);
  128.             if (y == p) {
  129.                 E[x].set(i, E[x].get(E[x].size() - 1));
  130.                 E[x].remove(E[x].size() - 1);
  131.                 --i;
  132.                 continue;
  133.             }
  134.             D[y] = D[x] + 1;
  135.             DFS1(y, x);
  136.             S[x] += y;
  137.         }
  138.         int mxs = -1;
  139.         for (int i = 0; i < E[x].size(); i++) {
  140.             int y = E[x].get(i);
  141.             if (mxs == -1 || S[mxs] < S[y])
  142.                 mxs = y;
  143.         }
  144.         to[x] = mxs;
  145.     }
  146.  
  147.     SegmentTree[] ST;
  148.     int[] ind;
  149.     int[] top;
  150.     void DFS2(int x) {
  151.         if (to[x] == -1) {
  152.             ST[x] = new SegmentTree(ind[x] + 1);
  153.         } else {
  154.             ind[to[x]] = ind[x] + 1;
  155.             top[to[x]] = top[x];
  156.         }
  157.         for (int y : E[x]) {
  158.             if (y != to[x])
  159.                 top[y] = y;
  160.         }
  161.         for (int y : E[x]) {
  162.             DFS2(y);
  163.         }
  164.         if (to[x] != -1) {
  165.             ST[x] = ST[to[x]];
  166.         }
  167.     }
  168.  
  169.     int lca(int a, int b) {
  170.         if (D[a] > D[b]) {
  171.             int t = a;
  172.             a = b;
  173.             b = t;
  174.         }
  175.         for (int d = lgn - 1; d >= 0; d--) {
  176.             if (D[b] - (1 << d) >= D[a])
  177.                 b = up[d][b];
  178.         }
  179.         if (a == b)
  180.             return a;
  181.         for (int d = lgn - 1; d >= 0; d--) {
  182.             if (up[d][a] != up[d][b]) {
  183.                 a = up[d][a];
  184.                 b = up[d][b];
  185.             }
  186.         }
  187.         if (a == b)
  188.             throw new AssertionError();
  189.         if (up[0][a] != up[0][b])
  190.             throw new AssertionError();
  191.         return up[0][a];
  192.     }
  193.  
  194.     class Query implements Comparable<Query> {
  195.         int a, b, x;
  196.         int id;
  197.         Query(int a, int b, int x, int id) {
  198.             this.a = a;
  199.             this.b = b;
  200.             this.x = x;
  201.             this.id = id;
  202.         }
  203.         @Override
  204.         public int compareTo(Query other) {
  205.             return -Integer.compare(this.x, other.x);
  206.         }
  207.     }
  208.  
  209.     Node get(int x, int y) {
  210.         Node res = null;
  211.         while (true) {
  212.             if (D[x] < D[y])
  213.  
  214.                 throw new AssertionError();
  215.             if (ST[x] == ST[y]) {
  216.                 res = combine(ST[x].get(ind[y] + 1, ind[x]), res);
  217.                 break;
  218.             } else {
  219.                 res = combine(ST[x].get(0, ind[x]), res);
  220.                 x = up[0][top[x]];
  221.             }
  222.         }
  223.         return res;
  224.     }
  225.  
  226.     public void run() {
  227.         int n = reader.nextInt();
  228.         int q = reader.nextInt();
  229.         F = new int[n];
  230.         for (int i = 1; i < n; i++) {
  231.             F[i] = reader.nextInt();
  232.         }
  233.         Edge[] edges = new Edge[n - 1];
  234.         for (int i = 0; i < n - 1; i++) {
  235.             int a = reader.nextInt() - 1;
  236.             int b = reader.nextInt() - 1;
  237.             int l = reader.nextInt();
  238.             edges[i] = new Edge(a, b, l);
  239.         }
  240.         E = new List[n];
  241.         for (int i = 0; i < n; i++)
  242.             E[i] = new ArrayList<Integer>(1);
  243.         for (Edge e : edges) {
  244.             E[e.a].add(e.b);
  245.             E[e.b].add(e.a);
  246.         }
  247.         while ((1 << lgn) < n + 1)
  248.             ++lgn;
  249.         up = new int[lgn][n];
  250.         S = new int[n];
  251.         to = new int[n];
  252.         D = new int[n];
  253.         DFS1(0, 0);
  254.         ST = new SegmentTree[n];
  255.         ind = new int[n];
  256.         top = new int[n];
  257.         DFS2(0);
  258.         Query[] Q = new Query[q];
  259.         for (int i = 0; i < q; i++) {
  260.             int a = reader.nextInt() - 1;
  261.             int b = reader.nextInt() - 1;
  262.             int l = reader.nextInt();
  263.             Q[i] = new Query(a, b, l, i);
  264.         }
  265.         Arrays.sort(edges);
  266.         Arrays.sort(Q);
  267.         int pte = 0;
  268.         int[] Ans = new int[q];
  269.         for (Query query : Q) {
  270.             while (pte != edges.length && edges[pte].l >= query.x) {
  271.                 int a = edges[pte].a;
  272.                 int b = edges[pte].b;
  273.                 if (up[0][b] == a) {
  274.                     int t = b;
  275.                     b = a;
  276.                     a = t;
  277.                 } else if (up[0][a] != b)
  278.                     throw new AssertionError();
  279.                 ST[a].set(ind[a], 1);
  280.                 pte++;
  281.             }
  282.             int a = query.a;
  283.             int b = query.b;
  284.             int l = lca(a, b);
  285.             Node u = get(a, l);
  286.             Node v = get(b, l);
  287.             if (v != null)
  288.                 v = v.reverse();
  289.             Node res = combine(v, u);
  290.             int ans = (res == null) ? 0 : res.value(); //!
  291.             Ans[query.id] = ans;
  292.         }
  293.         for (int a : Ans)
  294.             writer.printf("%d\n", a);
  295.     }
  296.  
  297.  
  298.     static class InputReader {
  299.         public BufferedReader reader;
  300.         public StringTokenizer tokenizer;
  301.  
  302.         public InputReader(InputStream stream) {
  303.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  304.             tokenizer = null;
  305.         }
  306.  
  307.         public String next() {
  308.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  309.                 try {
  310.                     tokenizer = new StringTokenizer(reader.readLine());
  311.                 } catch (IOException e) {
  312.                     throw new RuntimeException(e);
  313.                 }
  314.             }
  315.             return tokenizer.nextToken();
  316.         }
  317.  
  318.         public int nextInt() {
  319.             return Integer.parseInt(next());
  320.         }
  321.  
  322.         public double nextDouble() {
  323.             return Double.parseDouble(next());
  324.         }
  325.  
  326.         public long nextLong() {
  327.             return Long.parseLong(next());
  328.         }
  329.     }
  330.  
  331.     static class OutputWriter {
  332.         public PrintWriter writer;
  333.  
  334.         OutputWriter(OutputStream stream) {
  335.             writer = new PrintWriter(stream);
  336.         }
  337.  
  338.         public void printf(String format, Object... args) {
  339.             writer.print(String.format(Locale.ENGLISH, format, args));
  340.         }
  341.     }
  342. }
  343.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:4: error: class TaskE is public, should be declared in a file named TaskE.java
public class TaskE {
       ^
Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error
stdout
copy 
Standard output is empty
https://ideone.com/d2s583
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!