#851591 (Java21) No.399 動的な領主

提出ソース

結果

問題	No.399 動的な領主
ユーザー	ゆうき
提出日時	2023-03-22 10:06:29
言語	Java21 (openjdk 21)
結果	AC
実行時間	1,854 ms / 2,000 ms
コード長	11,072 bytes
コンパイル時間	3,427 ms
コンパイル使用メモリ	101,172 KB
実行使用メモリ	97,840 KB
最終ジャッジ日時	2024-09-18 14:48:31
合計ジャッジ時間	21,289 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	77 ms 38,012 KB
testcase_01	AC	79 ms 38,304 KB
testcase_02	AC	100 ms 39,248 KB
testcase_03	AC	96 ms 38,868 KB
testcase_04	AC	132 ms 40,996 KB
testcase_05	AC	363 ms 48,236 KB
testcase_06	AC	1,805 ms 87,576 KB
testcase_07	AC	1,747 ms 87,604 KB
testcase_08	AC	1,719 ms 87,608 KB
testcase_09	AC	1,699 ms 87,636 KB
testcase_10	AC	136 ms 41,588 KB
testcase_11	AC	280 ms 47,816 KB
testcase_12	AC	1,232 ms 88,412 KB
testcase_13	AC	1,155 ms 87,680 KB
testcase_14	AC	645 ms 96,732 KB
testcase_15	AC	813 ms 97,840 KB
testcase_16	AC	968 ms 93,596 KB
testcase_17	AC	1,854 ms 88,240 KB
testcase_18	AC	1,755 ms 87,700 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.*;
import java.util.stream.IntStream;

class Solver{
  static int infI = (int) 1e9;
  static long infL = (long) 1e18;
  //  static long mod = (int) 1e9 +7;
  static long mod = 998244353;
  static String yes = "Yes";
  static String no = "No";
  Random rd = ThreadLocalRandom.current();

  MyReader in = new MyReader(System.in);
  MyWriter out = new MyWriter(System.out);
  MyWriter log = new MyWriter(System.err){
    @Override
    protected void ln(){
      super.ln();
      flush();
    };
  };

  int N = in.it();
  Edge[] E = in.e(N,N -1);
  Edge[][] g = in.g(N,false,E);
  int[][] Q = in.qry(in.it());

  Object solve(){
    HLD hld = new HLD(E,g);
    LazySegmentTree seg = new LazySegmentTree(N,0L,i -> 0L){
      @Override
      protected long agg(long v0,long v1){ return v0 +v1; }

      @Override
      protected long map(long v,long f){ return v +f; }

      @Override
      protected long comp(long f0,long f1){ return f0 +f1; }

      @Override
      protected long powF(long f,int[] lr){ return f *lr[2]; }
    };

    long ans = 0;
    for (var q:Q) {
      var path = hld.path(q[0],q[1]);

      for (var p:path.path) {
        seg.upd(p[0],p[1],1L);
        ans += seg.get(p[0],p[1]);
      }
    }

    //    log.println(seg.c);
    return ans;
  }

}

class LazySegmentTree extends Seg{

  LazySegmentTree(int n,long e,IntFunction<Long> sup){ super(n,e,sup); }

  @Override
  void build(IntFunction<Long> sup){
    super.build(sup);
    for (int i = n;--i > 0;)
      merge(i);
  }

  @Override
  void upd(int l,int r,long f){
    down(l,r);
    super.upd(l,r,f);
    up(l,r);
  }

  @Override
  long get(int l,int r){
    down(l,r);
    return super.get(l,r);
  }
}

abstract class Seg{
  protected int n;
  private long e;
  private long[] val;
  private Long[] lazy;
  private int[][] lr;

  Seg(int n,long e,IntFunction<Long> sup){
    this.n = n;
    this.e = e;
    val = new long[n <<1];
    lazy = new Long[n];

    lr = new int[n <<1][];
    for (int i = n <<1;--i > 0;)
      lr[i] = i < n ? new int[]{lr[i <<1][0], lr[i <<1 |1][1], lr[i <<1][2] <<1} : new int[]{i, i +1, 1};
    build(sup);
  }

  void build(IntFunction<Long> sup){
    for (int i = 0;i < n;i++)
      val[i +n] = sup.apply(i);
  }

  protected long agg(long v0,long v1){ throw new UnsupportedOperationException("agg"); }

  protected long map(long v,long f){ throw new UnsupportedOperationException("map"); }

  protected long comp(long f0,long f1){ throw new UnsupportedOperationException("comp"); }

  protected long powF(long f,int[] lr){ throw new UnsupportedOperationException("powF"); }

  int c = 0;

  protected void merge(int i){
    if (i == 0)
      return;
    c++;
    val[i] = agg(eval(i <<1),eval(i <<1 |1));
  }

  private void uprec(int l,int r){
    while (0 < r) {
      merge(r >>= 1);
      if (l == r)
        l >>= 1;
      while (l > r)
        merge(l >>= 1);
    }
  }

  protected void up(int l,int r){
    l += n;
    r += n;
    uprec(l /(l &-l),r /(r &-r));
  }

  private void comp(int i,long f){
    if (i < n)
      lazy[i] = lazy[i] != null ? comp(lazy[i],f) : f;
    else
      val[i] = map(val[i],f);
  }

  private long eval(int i){
    if (i == 0)
      return e;

    if (i < n && lazy[i] != null) {
      val[i] = map(val[i],powF(lazy[i],lr[i]));
      for (int c = 0;c < 2;c++)
        comp(i <<1 |c,lazy[i]);
      lazy[i] = null;
    }

    return val[i];
  }

  private void downrec(int l,int r){
    if (0 < l && 0 < r)
      downrec(l >>1,r >>1);
    else if (0 < l)
      downrec(l >>1,r);
    else if (0 < r)
      downrec(l,r >>1);

    eval(l);
    if (l != r)
      eval(r);
  }

  protected void down(int l,int r){
    l += n;
    r += n;
    downrec(l /(l &-l),r /(r &-r));
  }

  void upd(int i,long f){ upd(i,i +1,f); }

  void upd(int l,int r,long f){
    l += n;
    r += n;
    do {
      if ((l &1) == 1)
        comp(l++,f);
      if ((r &1) == 1)
        comp(--r,f);
    } while ((l >>= 1) < (r >>= 1));
  }

  long get(int i){ return get(i,i +1); }

  long get(int l,int r){
    if (l >= r)
      return 0;
    l += n;
    r += n;
    long vl = e;
    long vr = e;
    do {
      if ((l &1) == 1)
        vl = agg(vl,eval(l++));
      if ((r &1) == 1)
        vr = agg(eval(--r),vr);
    } while ((l >>= 1) < (r >>= 1));

    return agg(vl,vr);
  }

}

class HLD{
  int n;
  Edge[] E;
  Edge[][] g;
  int[] size;
  int[] idx;

  int[] par;
  int[] hPar;
  int id = 0;

  HLD(Edge[] E,Edge[][] g){
    n = g.length;
    this.E = E;
    this.g = g;
    size = new int[n];
    idx = new int[n];
    par = new int[n];
    hPar = new int[n];
    dfs(0);
    dfs(0,0,0);
  }

  Path path(int u,int v){
    u = idx[u];
    v = idx[v];
    Path path = new Path();
    while (true) {
      if (u > v) {
        u ^= v;
        v ^= u;
        u ^= v;
      }

      int h = hPar[v];
      if (h <= u) {
        path.lca = u;
        path.add(u,v);
        break;
      }

      if (h != v)
        path.add(h +1,v);
      path.add(h,h);
      v = par[h];
    }

    return path;
  }

  private void dfs(int u){
    size[u]++;
    for (var e:g[u])
      if (size[e.v] == 0) {
        E[e.id] = e;
        dfs(e.v);
        size[u] += size[e.v];
      }
  }

  private void dfs(int u,int p,int hp){
    idx[u] = id;
    hPar[id] = hp;
    par[id] = idx[p];
    id++;
    int h = -1;
    for (var e:g[u])
      if (e.v != p && (h == -1 || size[h] < size[e.v]))
        h = e.v;
    if (h != -1)
      dfs(h,u,hp);
    for (var e:g[u])
      if (e.v != p && e.v != h)
        dfs(e.v,u,id);
  }

}

class Path{
  int lca;
  List<int[]> path = new ArrayList<>();

  void add(int a,int b){ path.add(new int[]{a, b +1}); }

}

class Edge{
  int id;
  int u;
  int v;
  long l;
  Edge rev;

  Edge(int id,int u,int v){
    this.id = id;
    this.u = u;
    this.v = v;
  }

  void rev(Edge rev){ rev.l = l; }

}

class Main{
  public static void main(String[] args) throws Exception{
    long st = System.currentTimeMillis();
    Solver solver = new Solver();
    Optional.ofNullable(solver.solve()).ifPresent(solver.out::println);
    solver.out.flush();
    solver.log.println(System.currentTimeMillis() -st);
  }
}

class MyReader{
  byte[] buf = new byte[1 <<16];
  int ptr = 0;
  int tail = 0;
  InputStream in;

  MyReader(InputStream in){ this.in = in; }

  byte read(){
    if (ptr == tail)
      try {
        tail = in.read(buf);
        ptr = 0;
      } catch (IOException e) {}
    return buf[ptr++];
  }

  boolean isPrintable(byte c){ return 32 < c && c < 127; }

  boolean isNum(byte c){ return 47 < c && c < 58; }

  byte nextPrintable(){
    byte ret = read();
    while (!isPrintable(ret))
      ret = read();
    return ret;
  }

  int it(){ return (int) lg(); }

  int[] it(int N){ return IntStream.range(0,N).map(i -> it()).toArray(); }

  int[][] it(int H,int W){ return arr(new int[H][],i -> it(W)); }

  int idx(){ return it() -1; }

  int[] idx(int N){ return IntStream.range(0,N).map(i -> idx()).toArray(); }

  int[][] idx(int H,int W){ return arr(new int[H][],i -> idx(W)); }

  int[][] qry(int Q){ return arr(new int[Q][],i -> new int[]{idx(), idx(), i}); }

  long lg(){
    byte i = nextPrintable();
    boolean negative = i == 45;
    long n = negative ? 0 : i -'0';
    while (isPrintable(i = read()))
      n = 10 *n +i -'0';
    return negative ? -n : n;
  }

  long[] lg(int N){ return IntStream.range(0,N).mapToLong(i -> lg()).toArray(); }

  long[][] lg(int H,int W){ return arr(new long[H][],i -> lg(W)); }

  double dbl(){ return Double.parseDouble(str()); }

  double[] dbl(int N){ return IntStream.range(0,N).mapToDouble(i -> dbl()).toArray(); }

  double[][] dbl(int H,int W){ return arr(new double[H][],i -> dbl(W)); }

  char[] ch(){ return str().toCharArray(); }

  char[][] ch(int H){ return arr(new char[H][],i -> ch()); }

  String line(){
    StringBuilder sb = new StringBuilder();

    for (byte c;(c = read()) != '\n';)
      sb.append((char) c);
    return sb.toString();
  }

  String str(){
    StringBuilder sb = new StringBuilder();
    sb.append((char) nextPrintable());

    for (byte c;isPrintable(c = read());)
      sb.append((char) c);
    return sb.toString();
  }

  String[] str(int N){ return arr(new String[N],i -> str()); }

  <T> T[] arr(T[] arr,IntFunction<T> f){
    Arrays.setAll(arr,f);
    return arr;
  }

  Edge[] e(int N,int M){ return e(N,M,e -> e.l = 1); }

  Edge[] e(int N,int M,Consumer<Edge> f){
    return arr(new Edge[M],i -> {
      Edge e = new Edge(i,idx(),idx());
      f.accept(e);
      return e;
    });
  }

  Edge[][] g(int N,int M,boolean b){ return g(N,b,e(N,M)); }

  Edge[][] g(int N,int M,boolean b,Consumer<Edge> f){ return g(N,b,e(N,M,f)); }

  Edge[][] g(int N,boolean b,Edge[] E){
    int[] c = new int[N];

    for (var e:E) {
      c[e.u]++;
      if (!b)
        c[e.v]++;
    }

    Edge[][] g = arr(new Edge[N][],i -> new Edge[c[i]]);

    for (var e:E) {

      g[e.u][--c[e.u]] = e;
      if (!b) {
        var rev = new Edge(e.id,e.v,e.u);
        e.rev(rev);
        g[e.v][--c[e.v]] = e.rev = rev;
      }
    }
    return g;
  }
}

class MyWriter{
  OutputStream out;
  byte[] buf = new byte[1 <<16];
  byte[] ibuf = new byte[20];
  int tail = 0;

  MyWriter(OutputStream out){ this.out = out; }

  void flush(){
    try {
      out.write(buf,0,tail);
      tail = 0;
    } catch (IOException e) {
      e.printStackTrace();
    }
  }

  private void sp(){ write((byte) ' '); }

  protected void ln(){ write((byte) '\n'); }

  private void write(byte b){
    buf[tail++] = b;
    if (tail == buf.length)
      flush();
  }

  private void write(byte[] b,int off,int len){
    for (int i = off;i < off +len;i++)
      write(b[i]);
  }

  private void write(long n){
    if (n < 0) {
      n = -n;
      write((byte) '-');
    }

    int i = ibuf.length;
    do {
      ibuf[--i] = (byte) (n %10 +'0');
      n /= 10;
    } while (n > 0);

    write(ibuf,i,ibuf.length -i);
  }

  private void write(Object obj){
    if (obj instanceof Boolean)
      write((boolean) obj ? Solver.yes : Solver.no);
    else if (obj instanceof Character)
      write((byte) (char) obj);
    else if (obj instanceof Integer)
      write((int) obj);
    else if (obj instanceof Long)
      write((long) obj);
    else if (obj instanceof char[])
      for (char b:(char[]) obj)
        write((byte) b);
    else if (obj.getClass().isArray()) {
      int l = Array.getLength(obj);
      boolean ln = false;

      if (0 < l) {
        Object a = Array.get(obj,0);
        ln = !(a instanceof char[]) && a.getClass().isArray();
      }
      for (int i = 0;i < l;i++) {
        write(Array.get(obj,i));
        if (i +1 < l)
          if (ln)
            ln();
          else
            sp();
      }
    } else
      for (char b:Objects.toString(obj).toCharArray())
        write((byte) b);
  }

  void println(Object obj){
    if (obj == null)
      return;
    write(obj);
    ln();
  }
}

yukicoder

結果

テストケース

ソースコード