結果
問題 |
No.3206 う し た ウ ニ 木 あ く ん 笑
|
ユーザー |
![]() |
提出日時 | 2025-07-18 23:24:11 |
言語 | Rust (1.83.0 + proconio) |
結果 |
RE
|
実行時間 | - |
コード長 | 3,566 bytes |
コンパイル時間 | 14,115 ms |
コンパイル使用メモリ | 397,436 KB |
実行使用メモリ | 33,432 KB |
最終ジャッジ日時 | 2025-07-18 23:24:29 |
合計ジャッジ時間 | 16,018 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 2 |
other | RE * 30 |
コンパイルメッセージ
warning: variable `L` should have a snake case name --> src/main.rs:41:18 | 41 | for (i, &L) in d.iter().enumerate() { | ^ help: convert the identifier to snake case: `l` | = note: `#[warn(non_snake_case)]` on by default
ソースコード
// -*- coding:utf-8-unix -*- #![allow(dead_code)] #![allow(unused_imports)] use std::cmp::*; use std::collections::*; use std::io::Write; const INF: i64 = 1223372036854775807; const MOD: i64 = 998244353; fn main() { let n: usize = read(); let edges: Vec<(usize, usize)> = (0..n-1).map(|_| { let (u, v) = readuu(); (u, v) }).collect(); let dp_all: Vec<Vec<usize>> = rerooting_dp( &edges, Vec::new(), |a: &Vec<usize>, b: &Vec<usize>| { let mut c = a.clone(); c.extend(b.iter()); c }, |_, _| Vec::from([0]), |a, _| { let mut v = a.clone(); for x in &mut v { *x += 1; } v }, ); let mut ans: i64 = 1; for depths in dp_all { let mut d = depths; d.sort_unstable_by(|a, b| b.cmp(a)); let mut best: i64 = 0; for (i, &L) in d.iter().enumerate() { let k = (i + 1) as i64; best = max(best, k * (L as i64)); } ans = max(ans, best + 1); } println!("{}", ans); } // --- rerooting library --- pub fn rerooting_dp<T, F, G, H>(edge: &[(usize, usize)], id: T, f: F, g: G, h: H) -> Vec<T> where T: Clone + Default + std::fmt::Debug, F: Fn(&T, &T) -> T, G: Fn(&T, usize) -> T, H: Fn(&T, usize) -> T, { let n = edge.len() + 1; let mut adj = vec![vec![]; n]; let mut ix_for_adj = vec![vec![]; n]; for &(i, j) in edge { ix_for_adj[i].push(adj[j].len()); ix_for_adj[j].push(adj[i].len()); adj[i].push(j); adj[j].push(i); } let mut order = Vec::with_capacity(n); let mut parent = vec![0; n]; let mut ix_for_parent = vec![0; n]; let mut stack = vec![0]; while let Some(i) = stack.pop() { order.push(i); for (ix, &j) in adj[i].iter().enumerate() { if j != parent[i] { stack.push(j); parent[j] = i; ix_for_parent[j] = ix; } } } let mut dp: Vec<_> = adj.iter().map(|a| vec![T::default(); a.len()]).collect(); for &i in order.iter().rev().skip(1) { let mut prod = id.clone(); for (ix, &j) in adj[i].iter().enumerate().filter(|&(_, &j)| j != parent[i]) { prod = f(&prod, &g(&dp[i][ix], j)); } dp[parent[i]][ix_for_parent[i]] = h(&prod, parent[i]); } let mut ret = vec![T::default(); n]; for &i in &order { let m = adj[i].len(); let mut accum_back = vec![T::default(); m]; *accum_back.last_mut().unwrap() = id.clone(); for j in (1..m).rev() { accum_back[j - 1] = f(&g(&dp[i][j], adj[i][j]), &accum_back[j]); } let mut accum = id.clone(); for (ix, &j) in adj[i].iter().enumerate() { let prod = f(&accum, &accum_back[ix]); dp[j][ix_for_adj[i][ix]] = h(&prod, j); accum = f(&accum, &g(&dp[i][ix], j)); } ret[i] = h(&accum, i); } ret } // --- IO helpers --- use std::io::{self, BufRead}; fn read<T: std::str::FromStr>() -> T { let stdin = io::stdin(); let line = stdin.lock().lines().next().unwrap().unwrap(); line.trim().parse().ok().unwrap() } fn readuu() -> (usize, usize) { let stdin = io::stdin(); let line = stdin.lock().lines().next().unwrap().unwrap(); let mut it = line.split_whitespace(); let u = it.next().unwrap().parse().unwrap(); let v = it.next().unwrap().parse().unwrap(); (u, v) }