結果
| 問題 |
No.399 動的な領主
|
| コンテスト | |
| ユーザー |
 ゆうき
|
| 提出日時 | 2023-03-22 10:20:09 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,486 ms / 2,000 ms |
| コード長 | 11,144 bytes |
| コンパイル時間 | 3,079 ms |
| コンパイル使用メモリ | 100,832 KB |
| 実行使用メモリ | 96,700 KB |
| 最終ジャッジ日時 | 2024-09-18 14:48:51 |
| 合計ジャッジ時間 | 17,460 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 19 |
ソースコード
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;
private int[] stk = new int[100];
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) {
while (l > r)
merge(l >>= 1);
merge(r >>= 1);
if (l == r)
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){
int s = 0;
while (0 < r) {
while (l > r) {
stk[++s] = l;
l >>= 1;
}
stk[++s] = r;
if (l == r)
l >>= 1;
r >>= 1;
}
while (0 < s)
eval(stk[--s]);
}
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();
}
}