結果
| 問題 |
No.763 Noelちゃんと木遊び
|
| コンテスト | |
| ユーザー |
 Haar
|
| 提出日時 | 2024-09-03 19:21:15 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 64 ms / 2,000 ms |
| コード長 | 13,670 bytes |
| コンパイル時間 | 12,054 ms |
| コンパイル使用メモリ | 400,552 KB |
| 実行使用メモリ | 31,216 KB |
| 最終ジャッジ日時 | 2025-03-22 10:44:23 |
| 合計ジャッジ時間 | 14,328 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 22 |
コンパイルメッセージ
warning: unused imports: `get`, `input`, and `utils::join_str::*` --> src/main.rs:7:9 | 7 | get, input, | ^^^ ^^^^^ ... 10 | utils::join_str::*, | ^^^^^^^^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default
ソースコード
// Bundled at 2024/09/03 19:20:39 +09:00
// Author: Haar
pub mod main {
use super::*;
use haar_lib::{
get, input,
tree::{tree_dp::*, *},
utils::fastio::*,
utils::join_str::*,
};
#[allow(unused_imports)]
use std::cell::RefCell;
use std::cmp::max;
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet};
#[allow(unused_imports)]
use std::io::Write;
#[allow(unused_imports)]
use std::rc::Rc;
#[derive(Clone, Default)]
pub struct Problem {}
impl Problem {
pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> {
let mut io = FastIO::new();
let n = io.read_usize();
let mut builder = TreeBuilder::new(n);
for _ in 0..n - 1 {
let u = io.read_usize() - 1;
let v = io.read_usize() - 1;
builder.extend(Some(TreeEdge::new(u, v, (), ())));
}
let tree = builder.build();
let id = (0, 0);
let up = Box::new(|a: (u64, u64), _| a);
let merge = Box::new(|a: (u64, u64), b: (u64, u64)| {
(a.0 + max(b.0 - 1, b.1), a.1 + max(b.0, b.1))
});
let apply = Box::new(|a: (u64, u64), _| (a.0 + 1, a.1));
let dp = TreeDP::new(id, merge, up, apply);
let dp = dp.run(&tree, 0);
let ans = max(dp[0].0, dp[0].1);
io.writeln(ans);
Ok(())
}
}
}
fn main() {
main::Problem::default().main().unwrap();
}
use crate as haar_lib;
pub mod macros {
pub mod io {
#[macro_export]
macro_rules! get {
( $in:ident, [$a:tt $(as $to:ty)*; $num:expr] ) => {
{
let n = $num;
(0 .. n).map(|_| get!($in, $a $(as $to)*)).collect::<Vec<_>>()
}
};
( $in:ident, ($($type:tt $(as $to:ty)*),*) ) => {
($(get!($in, $type $(as $to)*)),*)
};
( $in:ident, i8 ) => { $in.read_i64() as i8 };
( $in:ident, i16 ) => { $in.read_i64() as i16 };
( $in:ident, i32 ) => { $in.read_i64() as i32 };
( $in:ident, i64 ) => { $in.read_i64() };
( $in:ident, isize ) => { $in.read_i64() as isize };
( $in:ident, u8 ) => { $in.read_u64() as u8 };
( $in:ident, u16 ) => { $in.read_u64() as u16 };
( $in:ident, u32 ) => { $in.read_u64() as u32 };
( $in:ident, u64 ) => { $in.read_u64() };
( $in:ident, usize ) => { $in.read_u64() as usize };
( $in:ident, [char] ) => { $in.read_chars() };
( $in:ident, $from:tt as $to:ty ) => { <$to>::from(get!($in, $from)) };
}
#[macro_export]
macro_rules! input {
( @inner $in:ident, mut $name:ident : $type:tt ) => {
let mut $name = get!($in, $type);
};
( @inner $in:ident, mut $name:ident : $type:tt as $to:ty ) => {
let mut $name = get!($in, $type as $to);
};
( @inner $in:ident, $name:ident : $type:tt ) => {
let $name = get!($in, $type);
};
( @inner $in:ident, $name:ident : $type:tt as $to:ty ) => {
let $name = get!($in, $type as $to);
};
( $in:ident >> $($($names:ident)* : $type:tt $(as $to:ty)*),* ) => {
$(input!(@inner $in, $($names)* : $type $(as $to)*);)*
}
}
}
}
pub mod tree {
pub mod tree_dp {
use crate::tree::*;
pub struct TreeDP<'a, Weight, T> {
id: T,
merge: Box<dyn 'a + Fn(T, T) -> T>,
up: Box<dyn 'a + Fn(T, (usize, Weight)) -> T>,
apply: Box<dyn 'a + Fn(T, usize) -> T>,
}
impl<'a, Weight, T> TreeDP<'a, Weight, T>
where
Weight: Copy,
T: Clone,
{
pub fn new(
id: T,
merge: Box<impl 'a + Fn(T, T) -> T>,
up: Box<impl 'a + Fn(T, (usize, Weight)) -> T>,
apply: Box<impl 'a + Fn(T, usize) -> T>,
) -> Self {
Self {
id,
merge,
up,
apply,
}
}
pub fn run<E: TreeEdgeTrait<Weight = Weight>>(
&self,
tree: &Tree<E>,
root: usize,
) -> Vec<T> {
let size = tree.len();
let mut ret = vec![self.id.clone(); size];
self.__dfs(tree, root, None, &mut ret);
ret
}
fn __dfs<E: TreeEdgeTrait<Weight = Weight>>(
&self,
tree: &Tree<E>,
cur: usize,
par: Option<usize>,
ret: &mut Vec<T>,
) {
for e in tree.nodes[cur].neighbors() {
if Some(e.to()) == par {
continue;
}
self.__dfs(tree, e.to(), Some(cur), ret);
let temp = (self.up)(ret[e.to()].clone(), (e.to(), e.weight()));
ret[cur] = (self.merge)(ret[cur].clone(), temp);
}
ret[cur] = (self.apply)(ret[cur].clone(), cur);
}
}
}
pub trait TreeEdgeTrait {
type Weight;
fn from(&self) -> usize;
fn to(&self) -> usize;
fn weight(&self) -> Self::Weight;
fn rev(self) -> Self;
}
#[derive(Clone, Debug)]
pub struct TreeEdge<T, I> {
pub from: usize,
pub to: usize,
pub weight: T,
pub index: I,
}
impl<T, I> TreeEdge<T, I> {
pub fn new(from: usize, to: usize, weight: T, index: I) -> Self {
Self {
from,
to,
weight,
index,
}
}
}
impl<T: Clone, I> TreeEdgeTrait for TreeEdge<T, I> {
type Weight = T;
#[inline]
fn from(&self) -> usize {
self.from
}
#[inline]
fn to(&self) -> usize {
self.to
}
#[inline]
fn weight(&self) -> Self::Weight {
self.weight.clone()
}
fn rev(mut self) -> Self {
std::mem::swap(&mut self.from, &mut self.to);
self
}
}
#[derive(Clone, Debug, Default)]
pub struct TreeNode<E> {
pub parent: Option<E>,
pub children: Vec<E>,
}
impl<E: TreeEdgeTrait> TreeNode<E> {
pub fn neighbors(&self) -> impl DoubleEndedIterator<Item = &E> {
self.children.iter().chain(self.parent.iter())
}
pub fn neighbors_size(&self) -> usize {
self.children.len() + self.parent.as_ref().map_or(0, |_| 1)
}
}
pub struct TreeBuilder<E> {
nodes: Vec<TreeNode<E>>,
}
impl<E: TreeEdgeTrait + Clone> TreeBuilder<E> {
pub fn new(size: usize) -> Self {
Self {
nodes: vec![
TreeNode {
parent: None,
children: vec![],
};
size
],
}
}
pub fn extend(&mut self, edges: impl IntoIterator<Item = E>) {
for e in edges {
self.nodes[e.from()].children.push(e.clone());
self.nodes[e.to()].children.push(e.rev());
}
}
pub fn build(self) -> Tree<E> {
Tree {
nodes: self.nodes,
root: None,
}
}
}
pub struct RootedTreeBuilder<E> {
nodes: Vec<TreeNode<E>>,
root: usize,
}
impl<E: TreeEdgeTrait + Clone> RootedTreeBuilder<E> {
pub fn new(size: usize, root: usize) -> Self {
Self {
nodes: vec![
TreeNode {
parent: None,
children: vec![],
};
size
],
root,
}
}
pub fn extend(&mut self, edges: impl IntoIterator<Item = E>) {
for e in edges {
assert!(self.nodes[e.to()].parent.is_none());
self.nodes[e.from()].children.push(e.clone());
self.nodes[e.to()].parent.replace(e.rev());
}
}
pub fn build(self) -> Tree<E> {
Tree {
nodes: self.nodes,
root: Some(self.root),
}
}
}
#[derive(Clone, Debug)]
pub struct Tree<E> {
nodes: Vec<TreeNode<E>>,
root: Option<usize>,
}
impl<E> Tree<E> {
pub fn nodes_iter(&self) -> impl Iterator<Item = &TreeNode<E>> {
self.nodes.iter()
}
pub fn len(&self) -> usize {
self.nodes.len()
}
pub fn is_empty(&self) -> bool {
self.nodes.is_empty()
}
pub fn root(&self) -> Option<usize> {
self.root
}
}
}
pub mod utils {
pub mod fastio {
use std::fmt::Display;
use std::io::{Read, Write};
pub struct FastIO {
in_bytes: Vec<u8>,
in_cur: usize,
out_buf: std::io::BufWriter<std::io::Stdout>,
}
impl FastIO {
pub fn new() -> Self {
let mut s = vec![];
std::io::stdin().read_to_end(&mut s).unwrap();
let cout = std::io::stdout();
Self {
in_bytes: s,
in_cur: 0,
out_buf: std::io::BufWriter::new(cout),
}
}
#[inline]
pub fn getc(&mut self) -> Option<u8> {
if self.in_cur < self.in_bytes.len() {
self.in_cur += 1;
Some(self.in_bytes[self.in_cur])
} else {
None
}
}
#[inline]
pub fn peek(&self) -> Option<u8> {
if self.in_cur < self.in_bytes.len() {
Some(self.in_bytes[self.in_cur])
} else {
None
}
}
#[inline]
pub fn skip(&mut self) {
while self.peek().map_or(false, |c| c.is_ascii_whitespace()) {
self.in_cur += 1;
}
}
pub fn read_u64(&mut self) -> u64 {
self.skip();
let mut ret: u64 = 0;
while self.peek().map_or(false, |c| c.is_ascii_digit()) {
ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64;
self.in_cur += 1;
}
ret
}
pub fn read_u32(&mut self) -> u32 {
self.read_u64() as u32
}
pub fn read_usize(&mut self) -> usize {
self.read_u64() as usize
}
pub fn read_i64(&mut self) -> i64 {
self.skip();
let mut ret: i64 = 0;
let minus = if self.peek() == Some(b'-') {
self.in_cur += 1;
true
} else {
false
};
while self.peek().map_or(false, |c| c.is_ascii_digit()) {
ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64;
self.in_cur += 1;
}
if minus {
ret = -ret;
}
ret
}
pub fn read_i32(&mut self) -> i32 {
self.read_i64() as i32
}
pub fn read_isize(&mut self) -> isize {
self.read_i64() as isize
}
pub fn read_f64(&mut self) -> f64 {
self.read_chars()
.into_iter()
.collect::<String>()
.parse()
.unwrap()
}
pub fn read_chars(&mut self) -> Vec<char> {
self.skip();
let mut ret = vec![];
while self.peek().map_or(false, |c| c.is_ascii_graphic()) {
ret.push(self.in_bytes[self.in_cur] as char);
self.in_cur += 1;
}
ret
}
pub fn write_rev<T: Display>(&mut self, s: T) {
let mut s = format!("{}", s);
let s = unsafe { s.as_bytes_mut() };
s.reverse();
self.out_buf.write_all(s).unwrap();
}
pub fn write<T: Display>(&mut self, s: T) {
self.out_buf.write_all(format!("{}", s).as_bytes()).unwrap();
}
pub fn writeln_rev<T: Display>(&mut self, s: T) {
self.write_rev(s);
self.out_buf.write_all(&[b'\n']).unwrap();
}
pub fn writeln<T: Display>(&mut self, s: T) {
self.write(s);
self.out_buf.write_all(&[b'\n']).unwrap();
}
}
impl Drop for FastIO {
fn drop(&mut self) {
self.out_buf.flush().unwrap();
}
}
}
pub mod join_str {
pub trait JoinStr {
fn join_str(self, _: &str) -> String;
}
impl<T, I> JoinStr for I
where
T: ToString,
I: Iterator<Item = T>,
{
fn join_str(self, s: &str) -> String {
self.map(|x| x.to_string()).collect::<Vec<_>>().join(s)
}
}
}
}