結果
| 問題 | No.650 行列木クエリ |
| コンテスト | |
| ユーザー |
 sakikuroe
|
| 提出日時 | 2026-08-08 20:30:40 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 47 ms / 2,000 ms |
| + 600µs | |
| コード長 | 36,085 bytes |
| 記録 | |
| コンパイル時間 | 4,444 ms |
| コンパイル使用メモリ | 205,872 KB |
| 実行使用メモリ | 33,612 KB |
| 最終ジャッジ日時 | 2026-08-08 20:30:48 |
| 合計ジャッジ時間 | 6,256 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 10 |
コンパイルメッセージ
warning: unused import: `std::cmp`
--> src/main.rs:21:13
|
21 | use std::cmp;
| ^^^^^^^^
|
= note: `#[warn(unused_imports)]` (part of `#[warn(unused)]`) on by default
warning: unused imports: `arch::x86_64` and `sync`
--> src/main.rs:38:19
|
38 | use std::{arch::x86_64, sync};
| ^^^^^^^^^^^^ ^^^^
warning: unused import: `std::collections`
--> src/main.rs:164:13
|
164 | use std::collections;
| ^^^^^^^^^^^^^^^^
warning: unused import: `std::collections`
--> src/main.rs:176:13
|
176 | use std::collections;
| ^^^^^^^^^^^^^^^^
warning: unused import: `std::collections`
--> src/main.rs:185:13
|
185 | use std::collections;
| ^^^^^^^^^^^^^^^^
warning: unused import: `std::collections`
--> src/main.rs:193:13
|
193 | use std::collections;
| ^^^^^^^^^^^^^^^^
warning: unused import: `NotATreeError`
--> src/main.rs:195:34
|
195 | use super::graph::{self, NotATreeError};
| ^^^^^^^^^^^^^
warning: unused imports: `cmp` and `collections`
--> src/main.rs:216:19
|
216 | use std::{cmp, collections};
| ^^^ ^^^^^^^^^^^
warning: unused import: `dijkstra`
--> src/main.rs:598:21
|
598 | use super::{dijkstra, graph};
| ^^^^^^^^
warning: unused import: `std::collections`
--> src/main.rs:637:13
|
637 | use std::collections;
| ^^^^^^^^^^^^^^^^
warning: unused import: `std::collections`
--> src/main.rs:663:13
|
663 | use std::collections;
| ^^^^^^^^^^^^^^^^
warning: fields `root`, `order`, and `subtree_size` are never read
--> src/main.rs:354:13
|
353 | pub struct Hld {
| --- fields in this struct
354 | root: usize,
| ^^^^
...
359 |
ソースコード
// yukicoder: No.650 行列木クエリ
// https://yukicoder.me/problems/no/650
//
// anmitsu クレートを単一ファイルへ展開したうえで、この問題から到達しない
// コードを tools/bundle.py が自動で枝刈りしたものである。ジャッジは外部
// クレートへの依存を解決できないため、このファイル単体で完結させている。
mod algebra {
pub mod monoid {
use crate::algebra::semi_group;
pub trait Monoid: semi_group::SemiGroup {
fn id() -> Self::S;
}
}
pub mod semi_group {
use std::cmp;
pub trait SemiGroup {
type S;
fn op(a: &Self::S, b: &Self::S) -> Self::S;
}
}
}
mod modulo998244353 {
pub mod convolution_mont {
#![cfg(target_arch = "x86_64")]
use std::{arch::x86_64, sync};
}
}
mod ds {
pub mod segment_tree {
pub mod segment_tree_dense {
use super::super::super::algebra::monoid::Monoid;
// テストでのみ使用する追加のインポート. `monoid::AddMonoid` や `semi_group::SemiGroup` は
// 実装本体では使用しないため, `#[cfg(test)]` で分離する.
#[cfg(test)]
use super::super::super::algebra::{monoid, semi_group};
#[derive(Clone)]
pub struct SegmentTreeDense<M>
where
M: Monoid,
{
len: usize,
data: Vec<M::S>,
}
impl<M> SegmentTreeDense<M>
where
M: Monoid,
M::S: Clone,
{
pub fn new(n: usize) -> Self {
let len = n;
// The size of the internal data vector is 2*len - 1 for a complete binary tree.
// Handle the case where len is 0 to avoid underflow.
SegmentTreeDense::<M> {
len,
data: vec![M::id(); if len == 0 { 0 } else { 2 * len - 1 }],
}
}
pub fn len(&self) -> usize {
self.len
}
pub fn set(&mut self, mut idx: usize, x: M::S) {
assert!(
idx < self.len(),
"index out of bounds: the len is {} but the index is {}",
self.len(),
idx
);
// Calculate the position in the data vector corresponding to the leaf node.
idx += self.len - 1;
self.data[idx] = x;
}
pub fn build(&mut self) {
// Iterate from the last parent node down to the root.
for idx in (0..self.len - 1).rev() {
// Update parent node with the result of the monoid operation on its children.
self.data[idx] = M::op(&self.data[2 * idx + 1], &self.data[2 * idx + 2]);
}
}
pub fn update(&mut self, mut idx: usize, x: M::S) {
assert!(
idx < self.len(),
"index out of bounds: the len is {} but the index is {}",
self.len(),
idx
);
// Calculate leaf position and update its value.
idx += self.len - 1;
self.data[idx] = x;
// Climb up the tree updating parent nodes.
while idx > 0 {
idx = (idx - 1) / 2;
self.data[idx] = M::op(&self.data[2 * idx + 1], &self.data[2 * idx + 2]);
}
}
pub fn fold(&self, mut l: usize, mut r: usize) -> M::S {
if l >= r {
return M::id();
}
assert!(
r <= self.len(),
"index out of bounds: r must be less than or equal to the len (r: {}, len: {})",
r,
self.len()
);
// Map logical indices to internal data array indices.
l += self.len - 1;
r += self.len - 1;
let mut sum_l = M::id();
let mut sum_r = M::id();
// Fold elements within [l, r).
while l < r {
if l % 2 == 0 {
sum_l = M::op(&sum_l, &self.data[l]);
}
if r % 2 == 0 {
sum_r = M::op(&self.data[r - 1], &sum_r);
}
l /= 2;
r = (r - 1) / 2;
}
M::op(&sum_l, &sum_r)
}
}
}
}
}
mod graph {
pub mod bellman_ford {
use super::graph;
use std::collections;
impl<T: Copy + Ord + std::ops::Add<Output = T>> graph::Graph<T> {
}
impl<T> graph::Graph<T> {
}
}
pub mod bfs {
use super::graph;
use std::collections;
impl<T> graph::Graph<T> {
}
}
pub mod bipartite {
use super::graph;
use std::collections;
impl<T> graph::Graph<T> {
}
}
pub mod centroid_decomposition {
use std::collections;
use super::graph::{self, NotATreeError};
impl<T> graph::Graph<T> {
}
}
pub mod dfs {
use super::graph;
impl<T> graph::Graph<T> {
}
impl<T> graph::Graph<T> {
}
}
pub mod dijkstra {
use super::graph;
use std::{cmp, collections};
impl<T: Copy + Ord + std::ops::Add<Output = T>> graph::Graph<T> {
}
impl<T> graph::Graph<T> {
}
}
pub mod eulerian_path {
use super::graph;
impl<T> graph::Graph<T> {
}
}
pub mod floyd_warshall {
use super::graph;
impl<T: Copy + Ord + std::ops::Add<Output = T>> graph::Graph<T> {
}
impl<T> graph::Graph<T> {
}
}
pub mod graph {
pub struct Graph<T> {
pub(super) edges: Vec<Vec<(u32, T)>>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum NotATreeError {
Disconnected,
HasCycle,
}
pub(super) fn validate_tree<T>(g: &Graph<T>, root: usize) -> Result<(), NotATreeError> {
let n = g.vertex_count();
// root から到達できる頂点を反復深さ優先探索で辿り、親および各頂点の
// 子の本数を記録する。
let mut parent: Vec<Option<usize>> = vec![None; n];
let mut child_count = vec![0_usize; n];
let mut visited = vec![false; n];
visited[root] = true;
let mut visited_count = 1;
let mut stack = vec![root];
while let Some(u) = stack.pop() {
for (v, _) in g.edges(u) {
if !visited[v] {
visited[v] = true;
visited_count += 1;
parent[v] = Some(u);
child_count[u] += 1;
stack.push(v);
}
}
}
if visited_count < n {
return Err(NotATreeError::Disconnected);
}
// 各頂点の出次数が「親への1本 (根では0本) + 子の本数」とちょうど
// 一致することを確認する。多重辺や、対応する逆辺を欠いた辺があると、
// ここで不一致が生じる。
for u in 0..n {
let expected_out_degree = usize::from(parent[u].is_some()) + child_count[u];
if g.out_degree(u) != expected_out_degree {
return Err(NotATreeError::HasCycle);
}
}
Ok(())
}
impl<T> Graph<T> {
#[must_use]
pub fn new(n: usize) -> Self {
// vec![Vec::new(); n] は Vec<T> の Clone (延いては T: Clone) を要求してしまう。
// T に不要な制約を課さないよう、n 回 Vec::new() を呼び出す形で初期化する。
Graph {
edges: (0..n).map(|_| Vec::new()).collect::<Vec<Vec<(u32, T)>>>(),
}
}
pub fn vertex_count(&self) -> usize {
self.edges.len()
}
pub fn out_degree(&self, u: usize) -> usize {
self.edges[u].len()
}
pub fn edges(&self, u: usize) -> impl Iterator<Item = (usize, &T)> {
self.edges[u]
.iter()
.map(|(dst, payload)| (*dst as usize, payload))
}
pub fn add_edge(&mut self, src: usize, dst: usize, payload: T) {
debug_assert!(dst < self.vertex_count());
self.edges[src].push((dst as u32, payload));
}
}
impl<T: Clone> Graph<T> {
pub fn add_undirected_edge(&mut self, u: usize, v: usize, payload: T) {
self.add_edge(u, v, payload.clone());
self.add_edge(v, u, payload);
}
}
impl<T: Copy> Graph<T> {
}
}
pub mod hld {
use super::graph::{self, NotATreeError};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PathDirection {
Forward,
Reversed,
}
enum Frame {
Enter(usize, Option<usize>),
Leave(usize, Option<usize>),
}
pub struct Hld {
root: usize,
parent: Vec<Option<usize>>,
depth: Vec<usize>,
head: Vec<usize>,
id: Vec<usize>,
order: Vec<usize>,
subtree_size: Vec<usize>,
}
impl Hld {
pub fn depth(&self, v: usize) -> usize {
self.depth[v]
}
pub fn vertex_id(&self, v: usize) -> usize {
self.id[v]
}
pub fn edge_path_ranges(&self, u: usize, v: usize) -> Vec<(usize, usize, PathDirection)> {
self.path_ranges(u, v, true)
}
fn path_ranges(
&self,
mut u: usize,
mut v: usize,
exclude_lca: bool,
) -> Vec<(usize, usize, PathDirection)> {
// u_ranges/v_ranges は、それぞれ u/v が LCA に向かって登る際に
// 通過する区間を、登った順に集めたものである。いずれも「番号の
// 降順に読む」区間として扱う。
let mut u_ranges = Vec::new();
let mut v_ranges = Vec::new();
// 異なるパスに属する間は、パスの根元がより深い側の区間を切り出し、
// その親へ引き上げる。u と v の値そのものは入れ替えず、どちら側の
// 登りとして記録するかだけを、そのつど判定する。
while self.head[u] != self.head[v] {
if self.depth[self.head[u]] >= self.depth[self.head[v]] {
u_ranges.push((self.id[self.head[u]], self.id[u] + 1));
u = self.parent[self.head[u]].unwrap();
} else {
v_ranges.push((self.id[self.head[v]], self.id[v] + 1));
v = self.parent[self.head[v]].unwrap();
}
}
// 同じパスに入った時点で、浅い方が LCA になる。深い方の登りの列に、
// LCA までの最後の区間を追加する。
let (deeper_ranges, lca_id, deep_id) = if self.id[u] <= self.id[v] {
(&mut v_ranges, self.id[u], self.id[v])
} else {
(&mut u_ranges, self.id[v], self.id[u])
};
let start = if exclude_lca { lca_id + 1 } else { lca_id };
if start <= deep_id {
deeper_ranges.push((start, deep_id + 1));
}
// u 側は登った順のまま (降順に読む) 連結し、v 側は逆順にして
// (昇順に読む区間として) 連結する。
let mut ranges: Vec<(usize, usize, PathDirection)> = u_ranges
.into_iter()
.map(|(l, r)| (l, r, PathDirection::Reversed))
.collect();
ranges.extend(
v_ranges
.into_iter()
.rev()
.map(|(l, r)| (l, r, PathDirection::Forward)),
);
ranges
}
}
impl<T> graph::Graph<T> {
pub fn try_hld(&self, root: usize) -> Result<Hld, NotATreeError> {
graph::validate_tree(self, root)?;
let n = self.vertex_count();
// 第1段階: 深さ・親・部分木サイズを求める。木であることは検証済み
// のため、ここでは反復深さ優先探索でそのまま辿るだけでよい。
let mut parent: Vec<Option<usize>> = vec![None; n];
let mut depth = vec![0; n];
let mut subtree_size = vec![1; n];
let mut stack = vec![Frame::Enter(root, None)];
while let Some(frame) = stack.pop() {
match frame {
Frame::Enter(u, p) => {
stack.push(Frame::Leave(u, p));
parent[u] = p;
if let Some(p) = p {
depth[u] = depth[p] + 1;
}
for (v, _) in self.edges(u) {
if Some(v) != p {
stack.push(Frame::Enter(v, Some(u)));
}
}
}
Frame::Leave(u, p) => {
if let Some(p) = p {
subtree_size[p] += subtree_size[u];
}
}
}
}
// 第2段階: 各頂点について、部分木サイズが最大の子 (重い子) を求める。
let mut heavy_child: Vec<Option<usize>> = vec![None; n];
for (u, heavy_child) in heavy_child.iter_mut().enumerate() {
for (v, _) in self.edges(u) {
if parent[v] == Some(u) {
let is_heavier = match *heavy_child {
Some(current) => subtree_size[v] > subtree_size[current],
None => true,
};
if is_heavier {
*heavy_child = Some(v);
}
}
}
}
// 第3段階: 重い子を優先して辿ることで、パスに沿って連続した番号を
// 割り振る。スタックが後入れ先出しであることを利用し、軽い子を先に、
// 重い子を最後に積むことで、重い子を次に処理させ、同じパスの番号を
// 連続させる。
let mut id = vec![0; n];
let mut order = vec![0; n];
let mut head = vec![0; n];
let mut counter = 0;
let mut stack = vec![(root, root)];
while let Some((u, chain_head)) = stack.pop() {
id[u] = counter;
order[counter] = u;
head[u] = chain_head;
counter += 1;
for (v, _) in self.edges(u) {
if parent[v] == Some(u) && Some(v) != heavy_child[u] {
// 軽い子は、そこを頭とする新しいパスを始める。
stack.push((v, v));
}
}
if let Some(v) = heavy_child[u] {
stack.push((v, chain_head));
}
}
Ok(Hld {
root,
parent,
depth,
head,
id,
order,
subtree_size,
})
}
}
}
pub mod hld_path_query {
use super::super::algebra::monoid::Monoid;
use super::super::ds::segment_tree::segment_tree_dense::SegmentTreeDense;
use super::hld::{Hld, PathDirection};
pub struct HldPathQuery<'a, M: Monoid>
where
M::S: Clone,
{
hld: &'a Hld,
forward: SegmentTreeDense<M>,
reversed: SegmentTreeDense<M>,
}
impl<'a, M: Monoid> HldPathQuery<'a, M>
where
M::S: Clone,
{
pub fn new(hld: &'a Hld, values: &[M::S]) -> Self {
let n = values.len();
let mut forward = SegmentTreeDense::<M>::new(n);
let mut reversed = SegmentTreeDense::<M>::new(n);
for (v, value) in values.iter().enumerate() {
let id = hld.vertex_id(v);
forward.set(id, value.clone());
reversed.set(n - 1 - id, value.clone());
}
forward.build();
reversed.build();
Self {
hld,
forward,
reversed,
}
}
pub fn set_vertex(&mut self, v: usize, x: M::S) {
let n = self.forward.len();
let id = self.hld.vertex_id(v);
self.forward.update(id, x.clone());
self.reversed.update(n - 1 - id, x);
}
pub fn set_edge(&mut self, u: usize, v: usize, x: M::S) {
let child = if self.hld.depth(u) > self.hld.depth(v) {
u
} else {
v
};
self.set_vertex(child, x);
}
pub fn fold_edge_path(&self, u: usize, v: usize) -> M::S {
self.fold_ranges(self.hld.edge_path_ranges(u, v))
}
fn fold_ranges(&self, ranges: Vec<(usize, usize, PathDirection)>) -> M::S {
let n = self.forward.len();
// 区間の列を先頭から順に畳み込んでいく。acc がここまでの畳み込み
// 結果であり、区間ごとの値を M::op で右から結合していく。
ranges.into_iter().fold(M::id(), |acc, (l, r, dir)| {
// 区間の向きに応じて、参照するセグメント木を使い分ける。番号の
// 昇順に読みたい区間 (Forward) はそのまま forward から、降順に
// 読みたい区間 (Reversed) は、番号を反転させて構築してある
// reversed から、対応する反転後の区間 [n-r, n-l) を取り出す。
let value = match dir {
PathDirection::Forward => self.forward.fold(l, r),
PathDirection::Reversed => self.reversed.fold(n - r, n - l),
};
M::op(&acc, &value)
})
}
}
}
pub mod johnson {
use super::{dijkstra, graph};
impl<T: Copy + Ord + std::ops::Add<Output = T> + std::ops::Sub<Output = T>> graph::Graph<T> {
}
impl<T> graph::Graph<T> {
}
}
pub mod low_link {
use super::graph;
impl<T> graph::Graph<T> {
}
}
pub mod mst {
use super::graph;
impl<T: Copy + Ord> graph::Graph<T> {
}
impl<T> graph::Graph<T> {
}
}
pub mod scc {
use super::graph;
impl<T> graph::Graph<T> {
}
}
pub mod topological_sort {
use super::graph;
use std::collections;
impl<T> graph::Graph<T> {
}
}
pub mod tree_diameter {
use super::graph;
impl<T> graph::Graph<T> {
}
impl<T> graph::Graph<T> {
}
impl<T: Copy + Ord + std::ops::Add<Output = T> + Default> graph::Graph<T> {
}
}
pub mod zero_one_bfs {
use super::graph;
use std::collections;
impl<T> graph::Graph<T> {
}
}
}
mod io {
pub mod fastio {
use std::{ffi, fs, io, ptr};
#[cfg(target_os = "linux")]
use std::os::unix;
const OUT_BUF_SIZE: usize = 1 << 18;
const OUT_BUF_FLUSH_THRESHOLD: usize = 32;
const OUT_FLUSH_LIMIT: usize = OUT_BUF_SIZE - OUT_BUF_FLUSH_THRESHOLD;
fn is_8digits(mut bytes: u64) -> bool {
// 各バイトから '0' (0x30) を引き、上位ニブルが 0x30 になるかを見る代わりに、
// 0x30 との XOR を取ってから数字部分 (下位ニブル) を無視するマスクをかける。
// 数字であれば上位ニブルが 0 になり、全バイトの上位ニブルが 0 なら bytes は 0 になる。
bytes ^= 0x3030303030303030;
bytes &= 0xf0f0f0f0f0f0f0f0;
bytes == 0
}
fn parse_8digits(bytes: u64) -> u32 {
debug_assert!(is_8digits(bytes));
// SWAR (SIMD Within A Register) 法により、8 バイトの数字列を 3 段階の
// 乗算とビットシフトだけで 32 bit 整数へまとめて変換する。
// 各段階で隣接する 2 桁分の値を 1 つのフィールドへ合成していく。
let v1 = (bytes & 0x0f0f0f0f0f0f0f0f).wrapping_mul(0xA01) >> 8;
let v2 = (v1 & 0x00ff00ff00ff00ff).wrapping_mul(0x640001) >> 16;
let v3 = (v2 & 0x0000ffff0000ffff).wrapping_mul(0x271000000001) >> 32;
v3 as u32
}
pub trait FastWrite {
fn write_to(self, io: &mut Fastio);
fn writeln_to(self, io: &mut Fastio);
}
pub struct Fastio {
in_cursor: *const u8,
out_buf: Vec<u8>,
out_pos: usize,
out_capture: Option<Vec<u8>>,
_input_storage: Vec<u8>,
}
impl Fastio {
fn with_storage(mut input_storage: Vec<u8>, out_capture: Option<Vec<u8>>) -> Self {
// 8 桁ずつのパースの際に、末尾でメモリ外アクセスを起こさないよう、末尾に十分な番兵を追加しておく。
// 番兵には 0x00 を用いる。0x00 は数字 ('0'..='9') にならないため is_8digits は確実に false を
// 返し、かつ ASCII の空白文字 (0x20 以下) の範囲にも収まるため、chars や整数パースの
// 「空白以外/数字が続く間読み進める」ループも番兵の手前で正しく止まる。この 0x00 は、
// mmap 経路においてファイル末尾を含む最終ページの端数部分が OS によりゼロ埋めされる挙動とも
// 一致しており、両経路で番兵の性質を揃えられる。
input_storage.extend_from_slice(&[0_u8; 8]);
let in_cursor = input_storage.as_ptr();
Self {
in_cursor,
out_buf: vec![0_u8; OUT_BUF_SIZE],
out_pos: 0,
out_capture,
_input_storage: input_storage,
}
}
pub fn new() -> Self {
#[cfg(target_os = "linux")]
unsafe {
const PROT_READ: i32 = 0x1;
const MAP_PRIVATE: i32 = 0x02;
const MAP_FAILED: *mut ffi::c_void = (-1isize) as *mut ffi::c_void;
// /dev/stdin を通常ファイルとして開けない、あるいは mmap に失敗した場合は、
// 'mmap_try ブロックを抜けてフォールバック経路へ進む。
'mmap_try: {
let Ok(file) = fs::File::open("/dev/stdin") else {
break 'mmap_try;
};
let Ok(metadata) = file.metadata() else {
break 'mmap_try;
};
if !metadata.is_file() {
break 'mmap_try;
}
let len = metadata.len() as usize;
let fd = unix::io::AsRawFd::as_raw_fd(&file);
let addr = ptr::null_mut();
let mapped = mmap(addr, len, PROT_READ, MAP_PRIVATE, fd, 0);
if mapped == MAP_FAILED {
break 'mmap_try;
}
// mmap されたメモリ領域を直接読み取り対象とすることで、
// 標準入力全体をヒープへコピーするコストを避ける。
let in_cursor = mapped as *const u8;
return Self {
in_cursor,
out_buf: vec![0_u8; OUT_BUF_SIZE],
out_pos: 0,
out_capture: None,
_input_storage: vec![],
};
}
}
// mmap が使えない環境向けのフォールバック経路。標準入力を最後まで読み切って保持する。
let mut input_storage = vec![];
io::Read::read_to_end(&mut io::stdin().lock(), &mut input_storage)
.expect("failed to read from source");
Self::with_storage(input_storage, None)
}
pub fn char(&mut self) -> char {
unsafe {
self.skip_whitespace();
let ch = *self.in_cursor as char;
self.in_cursor = self.in_cursor.add(1);
ch
}
}
pub fn u64(&mut self) -> u64 {
unsafe {
self.skip_whitespace();
let mut value = 0_u64;
loop {
let bytes = ptr::read_unaligned(self.in_cursor as *const u64);
if !is_8digits(bytes) {
break;
}
value = value * 100_000_000_u64 + parse_8digits(bytes) as u64;
self.in_cursor = self.in_cursor.add(8);
}
while *self.in_cursor >= b'0' {
value = 10 * value + (*self.in_cursor - b'0') as u64;
self.in_cursor = self.in_cursor.add(1);
}
value
}
}
pub fn u32(&mut self) -> u32 {
unsafe {
self.skip_whitespace();
let mut value = 0_u32;
loop {
let bytes = ptr::read_unaligned(self.in_cursor as *const u64);
if !is_8digits(bytes) {
break;
}
value = value * 100_000_000 + parse_8digits(bytes);
self.in_cursor = self.in_cursor.add(8);
}
while *self.in_cursor >= b'0' {
value = 10 * value + (*self.in_cursor - b'0') as u32;
self.in_cursor = self.in_cursor.add(1);
}
value
}
}
pub fn flush(&mut self) {
self.out_flush();
}
#[inline(always)]
fn out_flush(&mut self) {
self.try_out_flush()
.expect("failed to write buffered output");
}
fn try_out_flush(&mut self) -> io::Result<()> {
if self.out_pos == 0 {
return Ok(());
}
// キャプチャモードの場合は、標準出力ではなくメモリ上のバッファへ書き写す。
if let Some(capture) = &mut self.out_capture {
capture.extend_from_slice(&self.out_buf[..self.out_pos]);
self.out_pos = 0;
return Ok(());
}
#[cfg(target_os = "linux")]
unsafe {
// write(2) は一度の呼び出しで全バイトを書き込むとは限らないため、
// 書き込み済みバイト数が対象範囲に達するまでループする。
let mut written = 0_usize;
let base = self.out_buf.as_ptr();
while written < self.out_pos {
let n = write(
1,
base.add(written) as *const ffi::c_void,
self.out_pos - written,
);
if n < 0 {
return Err(io::Error::last_os_error());
}
written += n as usize;
}
}
#[cfg(not(target_os = "linux"))]
{
let mut stdout = io::stdout().lock();
io::Write::write_all(&mut stdout, &self.out_buf[..self.out_pos])?;
io::Write::flush(&mut stdout)?;
}
self.out_pos = 0;
Ok(())
}
#[inline(always)]
fn out_maybe_flush(&mut self) {
if self.out_pos > OUT_FLUSH_LIMIT {
self.out_flush();
}
}
pub fn write<T>(&mut self, value: T)
where
T: FastWrite,
{
value.write_to(self);
}
#[inline(always)]
unsafe fn skip_whitespace(&mut self) {
unsafe {
while *self.in_cursor <= b' ' {
self.in_cursor = self.in_cursor.add(1);
}
}
}
}
impl Drop for Fastio {
fn drop(&mut self) {
// プロセス終了時の取りこぼしを防ぐため、可能な限り残りを出力する。
// Drop からはエラーを返せないため、失敗は握りつぶす。
let _ = self.try_out_flush();
}
}
impl FastWrite for char {
fn write_to(self, io: &mut Fastio) {
io.out_buf[io.out_pos] = self as u8;
io.out_pos += 1;
io.out_maybe_flush();
}
fn writeln_to(self, io: &mut Fastio) {
io.out_buf[io.out_pos] = self as u8;
io.out_pos += 1;
io.out_buf[io.out_pos] = b'\n';
io.out_pos += 1;
io.out_maybe_flush();
}
}
#[cfg(target_os = "linux")]
#[link(name = "c")]
unsafe extern "C" {
fn mmap(
addr: *mut ffi::c_void,
length: usize,
prot: i32,
flags: i32,
fd: i32,
offset: isize,
) -> *mut ffi::c_void;
fn write(fd: i32, buf: *const ffi::c_void, count: usize) -> isize;
}
}
}
use algebra::monoid::Monoid;
use algebra::semi_group::SemiGroup;
use graph::graph::Graph;
use graph::hld_path_query::HldPathQuery;
use io::fastio::Fastio;
const MOD: u64 = 1_000_000_007;
// この問題専用の 2x2 行列モノイド。root 側を左、leaf 側を右にして掛け合わせる
// 規約であり, op(a, b) は「a の後ろに b を掛ける (a * b)」を表す。
struct Matrix2x2Monoid;
impl SemiGroup for Matrix2x2Monoid {
type S = [[u64; 2]; 2];
fn op(a: &Self::S, b: &Self::S) -> Self::S {
let mut c = [[0_u64; 2]; 2];
for (i, row) in c.iter_mut().enumerate() {
for (j, cell) in row.iter_mut().enumerate() {
let mut sum = 0_u128;
for k in 0..2 {
sum += u128::from(a[i][k]) * u128::from(b[k][j]);
}
*cell = (sum % u128::from(MOD)) as u64;
}
}
c
}
}
impl Monoid for Matrix2x2Monoid {
fn id() -> Self::S {
[[1, 0], [0, 1]]
}
}
// Fastio の数値書き込みは write/writeln のどちらを使っても改行文字まで出力してしまうため、
// この問題のように「行列の4要素を同じ行に並べる」形式には使えない。
// char の書き込みだけは改行を伴わないため、あらかじめ文字列化したトークン列を
// 1文字ずつ書き込むことで、任意の内容を1行にまとめて出力する。
fn write_line(io: &mut Fastio, tokens: &[String]) {
for (i, token) in tokens.iter().enumerate() {
if i > 0 {
io.write(' ');
}
for c in token.chars() {
io.write(c);
}
}
io.write('\n');
}
fn main() {
let mut io = Fastio::new();
let n = io.u32() as usize;
let edges = (0..n - 1)
.map(|_| {
let a = io.u32() as usize;
let b = io.u32() as usize;
(a, b)
})
.collect::<Vec<(usize, usize)>>();
let mut g = Graph::new(n);
for &(a, b) in &edges {
g.add_undirected_edge(a, b, ());
}
let hld = g.try_hld(0).unwrap();
// 各辺の初期値は単位行列であり、頂点の初期値としても (どの頂点が
// どの辺に対応するかによらず) 同じ値になる。
let identity = Matrix2x2Monoid::id();
let mut path_query = HldPathQuery::<Matrix2x2Monoid>::new(&hld, &vec![identity; n]);
let q = io.u32() as usize;
for _ in 0..q {
let kind = io.char();
if kind == 'x' {
let i = io.u32() as usize;
let x00 = io.u64();
let x01 = io.u64();
let x10 = io.u64();
let x11 = io.u64();
let (a, b) = edges[i];
path_query.set_edge(a, b, [[x00, x01], [x10, x11]]);
} else {
let i = io.u32() as usize;
let j = io.u32() as usize;
let m = path_query.fold_edge_path(i, j);
write_line(
&mut io,
&[
m[0][0].to_string(),
m[0][1].to_string(),
m[1][0].to_string(),
m[1][1].to_string(),
],
);
}
}
io.flush();
}