結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
コンテスト
ユーザー Moss_Local
提出日時 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

ソースコード

diff #
raw source code 

// -*- 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)
}
0