結果
| 問題 | No.3113 The farthest point |
| ユーザー |
 haihamabossu
|
| 提出日時 | 2025-04-19 00:22:18 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 413 ms / 2,000 ms |
| コード長 | 7,402 bytes |
| コンパイル時間 | 12,736 ms |
| コンパイル使用メモリ | 399,616 KB |
| 実行使用メモリ | 86,876 KB |
| 最終ジャッジ日時 | 2025-04-19 00:22:40 |
| 合計ジャッジ時間 | 20,348 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 33 |
ソースコード
pub mod rerooting {
use super::tree::{Edge, Tree};
pub struct RerootingResult<T: Clone> {
pub dp: Vec<Vec<T>>,
pub suml: Vec<Vec<T>>,
pub sumr: Vec<Vec<T>>,
}
impl<T: Clone> RerootingResult<T> {
pub fn new(tree: &Tree, init: T) -> Self {
let mut dp: Vec<Vec<T>> = vec![];
let mut suml: Vec<Vec<T>> = vec![];
let mut sumr: Vec<Vec<T>> = vec![];
for u in 0..tree.n {
dp.push(vec![init.clone(); tree.degree(u)]);
suml.push(vec![init.clone(); tree.degree(u) + 1]);
sumr.push(vec![init.clone(); tree.degree(u) + 1]);
}
Self { dp, suml, sumr }
}
}
pub fn rerooting<T: Clone>(
tree: &Tree,
init: T,
fold: impl Fn(&T, &T) -> T,
add: impl Fn(&T, usize, &Edge) -> T,
) -> RerootingResult<T> {
let mut res = RerootingResult::<T>::new(tree, init.clone());
let mut sum = vec![init.clone(); tree.n];
for &u in &tree.post_order {
for (i, edge) in tree.edges[u].iter().enumerate() {
if Some(edge.to) == tree.parent[u] {
continue;
}
res.dp[u][i] = add(&sum[edge.to], u, edge);
sum[u] = fold(&sum[u], &res.dp[u][i]);
}
}
for &u in &tree.pre_order {
for (i, edge) in tree.edges[u].iter().enumerate() {
if Some(edge.to) == tree.parent[u] {
let &Edge { to: v, rev, .. } = edge;
res.dp[u][i] = add(&fold(&res.suml[v][rev], &res.sumr[v][rev + 1]), u, edge);
}
}
for i in 0..tree.degree(u) {
res.suml[u][i + 1] = fold(&res.suml[u][i], &res.dp[u][i]);
}
for i in (0..tree.degree(u)).rev() {
res.sumr[u][i] = fold(&res.sumr[u][i + 1], &res.dp[u][i]);
}
}
res
}
}
pub mod scanner {
pub struct Scanner {
buf: Vec<String>,
}
impl Scanner {
pub fn new() -> Self {
Self { buf: vec![] }
}
pub fn new_from(source: &str) -> Self {
let source = String::from(source);
let buf = Self::split(source);
Self { buf }
}
pub fn next<T: std::str::FromStr>(&mut self) -> T {
loop {
if let Some(x) = self.buf.pop() {
return x.parse().ok().expect("");
}
let mut source = String::new();
std::io::stdin().read_line(&mut source).expect("");
self.buf = Self::split(source);
}
}
fn split(source: String) -> Vec<String> {
source
.split_whitespace()
.rev()
.map(String::from)
.collect::<Vec<_>>()
}
}
}
pub mod tree {
#[derive(Clone)]
pub struct Edge {
pub to: usize,
pub id: usize,
pub rev: usize,
pub cost: isize,
}
pub struct Tree {
pub n: usize,
root: usize,
pub edges: Vec<Vec<Edge>>,
pub parent: Vec<Option<usize>>,
pub depth: Vec<usize>,
pub subtree_size: Vec<usize>,
pub pre_order: Vec<usize>,
pub post_order: Vec<usize>,
pub euler_tour: Vec<usize>,
}
impl Tree {
pub fn new(n: usize) -> Tree {
Tree {
n,
root: 0,
edges: vec![vec![]; n],
parent: vec![None; n],
depth: vec![0; n],
subtree_size: vec![0; n],
pre_order: vec![],
post_order: vec![],
euler_tour: vec![],
}
}
pub fn init(scanner: &mut crate::scanner::Scanner, indexed: usize, weighted: bool) -> Tree {
let n: usize = scanner.next();
let mut tree = Tree::new(n);
for id in 0..n - 1 {
let u: usize = scanner.next::<usize>() - indexed;
let v: usize = scanner.next::<usize>() - indexed;
let cost: isize;
if weighted {
cost = scanner.next();
} else {
cost = 1;
}
tree.add_edge(u, v, id, cost);
}
tree.set_root(0);
tree
}
pub fn add_edge(&mut self, u: usize, v: usize, id: usize, cost: isize) {
{
let to = v;
let rev = self.edges[v].len();
self.edges[u].push(Edge { to, id, rev, cost });
}
{
let to = u;
let rev = self.edges[u].len() - 1;
self.edges[v].push(Edge { to, id, rev, cost });
}
}
pub fn degree(&self, u: usize) -> usize {
self.edges[u].len()
}
pub fn set_root(&mut self, root: usize) {
let n = self.n;
self.root = root;
self.parent = vec![None; n];
self.depth = vec![0; n];
self.subtree_size = vec![0; n];
self.pre_order = vec![];
self.post_order = vec![];
self.euler_tour = vec![];
let mut stack: Vec<(usize, usize, usize)> = vec![];
stack.push((root, 0, 0));
while let Some((u, i, d)) = stack.pop() {
if i == 0 {
self.subtree_size[u] += 1;
self.pre_order.push(u);
}
if i == self.degree(u) {
if let Some(p) = self.parent[u] {
self.subtree_size[p] += self.subtree_size[u];
}
self.post_order.push(u);
self.euler_tour.push(u);
continue;
}
stack.push((u, i + 1, d));
let edge = &self.edges[u][i];
if Some(edge.to) == self.parent[u] {
continue;
}
self.parent[edge.to] = Some(u);
self.depth[edge.to] = d + 1;
self.euler_tour.push(u);
stack.push((edge.to, 0, d + 1));
}
}
}
}
use crate::{
rerooting::rerooting,
scanner::Scanner,
tree::{Edge, Tree},
};
use std::io::Write;
fn main() {
let mut scanner = Scanner::new();
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
solve(&mut scanner, &mut out);
}
fn solve(scanner: &mut Scanner, out: &mut std::io::BufWriter<std::io::StdoutLock>) {
let n: usize = scanner.next();
let mut tree = Tree::new(n);
for id in 0..n - 1 {
let u: usize = scanner.next::<usize>() - 1;
let v: usize = scanner.next::<usize>() - 1;
let w: isize = scanner.next::<isize>();
tree.add_edge(u, v, id, w);
}
tree.set_root(0);
let fold = |lhs: &isize, rhs: &isize| -> isize { *lhs.max(rhs) };
let add = |x: &isize, _parent: usize, edge: &Edge| -> isize { x + edge.cost };
let res = rerooting(&tree, 0, fold, add);
let mut ans = 0;
for i in 0..n {
ans = ans.max(res.sumr[i][0]);
}
writeln!(out, "{}", ans).unwrap();
}