結果
| 問題 | No.3206 う し た ウ ニ 木 あ く ん 笑 |
| コンテスト | |
| ユーザー |
 sorachandu
|
| 提出日時 | 2026-03-05 18:35:38 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,445 bytes |
| 記録 | |
| コンパイル時間 | 9,897 ms |
| コンパイル使用メモリ | 351,652 KB |
| 実行使用メモリ | 77,764 KB |
| 最終ジャッジ日時 | 2026-03-05 18:37:07 |
| 合計ジャッジ時間 | 10,026 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 9 WA * 21 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#pragma region templates
struct Init { Init() { ios::sync_with_stdio(0); cin.tie(0); cout << setprecision(13); } }init;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using i128= __int128_t;
template<typename T> using minpq=priority_queue<T,vector<T>,greater<T>>;
#define rep(i, x, limit) for(int i=(x); i< (limit); ++i)
#define REP(i, x, limit) for(int i=(x); i<=(limit); ++i)
#define all(x) std::begin(x), std::end(x)
#define rall(x) std::rbegin(x), std::rend(x)
#define el '\n'
#define spa ' '
#define Yes cout<<"Yes"<<el
#define No cout<<"No" <<el
#define YES cout<<"YES"<<el
#define NO cout<<"NO" <<el
#define END(x) cout<<(x)<<el, exit(0)
#define debug(x) cerr<<#x<<" = "<<x<<el
[[maybe_unused]] const int inf = 1073741823;
[[maybe_unused]] const ll infl = 1LL << 60;
std::string i128_to_str(const __int128_t &target){
std::string res_str;
__uint128_t target_tmp = target<0 ? -target : target;
do{
res_str+=target_tmp%10+'0';
target_tmp/=10;
}while(target_tmp!=0);
if(target<0) res_str+='-';
std::reverse(std::begin(res_str),std::end(res_str));
return res_str;
}
// is_pair
template<typename T> constexpr bool is_pair_v = false;
template<typename T, typename U> constexpr bool is_pair_v<std::pair<T,U>> = true;
// istreamable
#if __cplusplus >= 202002L
template<typename T> concept istreamable_v = requires(T a){ std::cin>>a; };
#else // earlier C++20
template<typename T, typename=void> constexpr bool istreamable_v = false;
template<typename T> constexpr bool istreamable_v<T, std::void_t<decltype(std::cin>>std::declval<T&>())>> = true;
#endif
// ostreamable
#if __cplusplus >= 202002L
template<typename T> concept ostreamable_v = requires(T a){ std::cout<<a; };
#else // earlier C++20
template<typename T, typename=void> constexpr bool ostreamable_v = false;
template<typename T> constexpr bool ostreamable_v<T, std::void_t<decltype(std::cout<<std::declval<T&>())>> = true;
#endif
// iterable
#if __cplusplus >= 202002L
# if __has_include(<ranges>)
template<typename T> concept iterable_v = std::ranges::range<T>;
# else // C++20, not has <ranges>
template<typename T> concept iterable_v = requires(T a){ std::begin(a); std::end(a); };
# endif
#else // earlier C++20
template<typename T> constexpr bool iterable_v = std::is_same_v<decltype(std::begin(std::declval<T>())), decltype(std::end(std::declval<T>()))>;
#endif
// concepts for debug use only:
#if __cplusplus >= 202002L
// stack_like_v (std::stack, std::priority_queue)
template<typename T> concept stack_like_v = requires(T t){
requires(
std::same_as<decltype(t.top()), typename T::reference> ||
std::same_as<decltype(t.top()), typename T::const_reference>
);
{ t.pop() };
{ t.empty() } -> std::same_as<bool>;
};
// queue_like_v (std::queue)
template<typename T> concept queue_like_v = requires(T t){
{ t.front() } -> std::same_as<typename T::reference&>;
{ t.pop() };
{ t.empty() } -> std::same_as<bool>;
};
#endif
void input(){ return; }
template<typename T, typename... Rest>
void input(T &target, Rest&... rest){
if constexpr(istreamable_v<T>) cin>>target;
else if constexpr(iterable_v<T>) for(auto &e:target) input(e);
else if constexpr(is_pair_v<T>){
input(target.first);
input(target.second);
}else if constexpr(std::is_convertible_v<long long, T>){
long long val;
input(val);
target=val;
}else{
cerr<<"Invalid Input: Unreadable variable detected"<<std::endl;
assert(false);
}
input(rest...);
}
// output for debugging
template<typename T>
void write_value(const T &target){
using V = std::decay_t<T>;
if constexpr(ostreamable_v<V>){
std::cout<<target;
}else if constexpr(is_pair_v<V>){
std::cout<<'{';
write_value(target.first);
std::cout<<',';
write_value(target.second);
std::cout<<'}';
}else if constexpr(iterable_v<V>){
std::cout<<'[';
bool first=true;
for(const auto &e:target){
if(!first) std::cout<<", ";
write_value(e);
first=false;
}
std::cout<<']';
}else if constexpr(std::is_convertible<V, __int128_t>::value){
write_value(i128_to_str(target));
}else if constexpr(std::is_convertible_v<V, long long>){
write_value(static_cast<long long>(target));
}else if constexpr(stack_like_v<V>){
auto tmp=target;
std::cout<<'[';
bool first=true;
while(!tmp.empty()){
if(!first) std::cout<<", ";
write_value(tmp.top());
tmp.pop();
first=false;
}
std::cout<<']';
}else if constexpr(queue_like_v<V>){
auto tmp=target;
std::cout<<'[';
bool first=true;
while(!tmp.empty()){
if(!first) std::cout<<", ";
write_value(tmp.front());
tmp.pop();
first=false;
}
std::cout<<']';
}
else{
std::cerr<<"Invalid Output: Unwritable variable detected"<<std::endl;
assert(false);
}
}
void output(){ std::cout<<'\n'; }
template<typename T, typename... Rest>
void output(const T &target, const Rest&... rest){
write_value(target);
if constexpr(sizeof...(rest)>0){
std::cout<<' ';
output(rest...);
}else{
std::cout<<'\n';
}
}
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){return a>b?a=b,true:false;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){return a<b?a=b,true:false;}
// a^bを返す オーバーフローに注意
ll Pow(ll a,ll b){
assert(b>=0);
if(a==0 and b==0) return 1;
if(a==1) return 1;
if(a==-1) return (b&1)?-1:1;
ll res=1;
while(b){
if(b&1) res*=a;
b>>=1;
if(b) a*=a;
}
return res;
}
// 二分探索による、浮動小数点型を介さないsqrt
// 制約：0 <= x <= LLONG_MAX
ll ll_sqrt(ll x){
assert(0 <= x);
ll ok = 0, ng = x/2+2;
while(abs(ok-ng) > 1){
ll mid = (ok+ng)/2;
if(x/mid < mid) ng = mid;
else ok = mid;
}
return ok;
}
// 浮動小数点型を介さず、aを底とした対数関数 log_a(x)以上の最小の整数を返す
// 制約: 0 < x <= LLONG_MAX, 1 < a <= LLONG_MAX
ll ll_log(ll x, ll a = 2){
assert(x > 0 && a > 1);
ll res = 0;
while(x > 1){
x = (x+a-1)/a;
res++;
}
return res;
}
// Pythonのenumerateみたいなやつ [index,value]を範囲for文に提供
template<typename T> vector<pair<int,T>> enumerate(const vector<T> &v){
vector<pair<int,T>> res(ssize(v));
for(int i=0;i<ssize(v);i++) res[i]={i,v[i]};
return res;
}
vector<pair<int,char>> enumerate(const string &s){
vector<pair<int,char>> res(ssize(s));
for(int i=0;i<ssize(s);i++) res[i]={i,s[i]};
return res;
}
// This function sorts multiple vectors based on the first vector
// and returns the indices of the sorted order.
// Note: First argument is a comparison function.
template <typename Compare, typename... Vectors>
vector<size_t> multipleSort(Compare comp = Compare(), Vectors&... vectors) {
const size_t size = std::get<0>(std::tie(vectors...)).size();
((void)std::initializer_list<int>{(vectors.size() == size ? 0 :
throw std::invalid_argument("Vectors must have the same size"))...});
std::vector<size_t> indices(size);
std::iota(indices.begin(), indices.end(), 0);
std::sort(indices.begin(), indices.end(), [&](size_t i, size_t j) {
return comp(std::get<0>(std::tie(vectors...))[i], std::get<0>(std::tie(vectors...))[j]);
});
auto reorder = [&](auto& vec) {
auto temp=vec;
for (size_t i = 0; i < size; ++i) {
vec[i] = temp[indices[i]];
}
};
(reorder(vectors), ...);
return indices;
}
#pragma endregion templates
/*//--------------------------------------------------------
refer to: https://trap.jp/post/1702/ noya2さんに感謝
全方位木DP モノイドを載せて全頂点それぞれ根としてN回木DPする感じ.
Eがメインの型、Vは辺のポテンシャルの型という感じだが基本E==Vでよい
merge: Eの二項演算(モノイド)を載せて、部分木同士を合併 e(): 単位元
put_edge: 辺を移動するときに値(E)に何か作用させる感じ. ポテンシャル等.
+1とかはここに書くがち(merge(a,e())=aを意識して.)
put_vertex: dp[頂点]に値を書く. つまりmergeで得た値E valがあって
dp[頂点]=put_vertex(val)って感じ. +1とかも同上.
put_edge, put_vertexのiはよくわかんない… 基本無視でok
build(root=0)の返り値でroot中心の木DP結果が見れる
*///--------------------------------------------------------
template <class E, class V, E (*merge)(E, E), E (*e)(), E (*put_edge)(V, int), V (*put_vertex)(E, int)>
struct RerootingDP {
struct edge {
int to, idx, xdi;
};
RerootingDP(int n_ = 0) : n(n_), inner_edge_id(0) {
es.resize(2*n-2);
start.resize(2*n-2);
if (n == 1) es_build();
}
void add_edge(int u, int v, int idx, int xdi){
start[inner_edge_id] = u;
es[inner_edge_id] = {v,idx,xdi};
inner_edge_id++;
start[inner_edge_id] = v;
es[inner_edge_id] = {u,xdi,idx};
inner_edge_id++;
if (inner_edge_id == 2*n-2){
es_build();
}
}
vector<V> build(int root_ = 0){
root = root_;
vector<V> subdp(n); subdp[0] = put_vertex(e(),0);
outs.resize(n);
vector<int> geta(n+1,0);
for (int i = 0; i < n; i++) geta[i+1] = start[i+1] - start[i] - 1;
geta[root+1]++;
for (int i = 0; i < n; i++) geta[i+1] += geta[i];
auto dfs = [&](auto sfs, int v, int f) -> void {
E val = e();
for (int i = start[v]; i < start[v+1]; i++){
if (es[i].to == f){
swap(es[start[v+1]-1],es[i]);
}
if (es[i].to == f) continue;
sfs(sfs,es[i].to,v);
E nval = put_edge(subdp[es[i].to],es[i].idx);
outs[geta[v]++] = nval;
val = merge(val,nval);
}
subdp[v] = put_vertex(val, v);
};
dfs(dfs,root,-1);
return subdp;
}
vector<V> reroot(){
vector<E> reverse_edge(n);
reverse_edge[root] = e();
vector<V> answers(n);
auto dfs = [&](auto sfs, int v) -> void {
int le = outs_start(v);
int ri = outs_start(v+1);
int siz = ri - le;
vector<E> rui(siz+1);
rui[siz] = e();
for (int i = siz-1; i >= 0; i--){
rui[i] = merge(outs[le+i],rui[i+1]);
}
answers[v] = put_vertex(merge(rui[0],reverse_edge[v]),v);
E lui = e();
for (int i = 0; i < siz; i++){
V rdp = put_vertex(merge(merge(lui,rui[i+1]),reverse_edge[v]),v);
reverse_edge[es[start[v]+i].to] = put_edge(rdp,es[start[v]+i].xdi);
lui = merge(lui,outs[le+i]);
sfs(sfs,es[start[v]+i].to);
}
};
dfs(dfs,root);
return answers;
}
private:
int n, root, inner_edge_id;
vector<E> outs;
vector<edge> es;
vector<int> start;
int outs_start(int v){
int res = start[v] - v;
if (root < v) res++;
return res;
}
void es_build(){
vector<edge> nes(2*n-2);
vector<int> nstart(n+2,0);
for (int i = 0; i < 2*n-2; i++) nstart[start[i]+2]++;
for (int i = 0; i < n; i++) nstart[i+1] += nstart[i];
for (int i = 0; i < 2*n-2; i++) nes[nstart[start[i]+1]++] = es[i];
swap(es,nes);
swap(start,nstart);
}
};
struct node{
ll ma,mi,cnt,val;
};
node merge(node a,node b){
return {max(a.ma,b.ma),min(a.mi,b.mi),a.cnt+b.cnt,0};
}
node e(){ return {-inf,inf,0,0}; }
node put_edge(node V,int idx){
V.mi++;
V.ma++;
V.cnt++;
return V;
}
node put_vertex(node E,int v){
if(E.mi==inf) E.mi=0;
if(E.ma==-inf) E.ma=0;
if(E.cnt==1) E.val=E.ma+1;
else E.val=E.mi*E.cnt+1;
E.cnt=0;
return E;
}
int main(){
/*//--------------------------------------------------------
ある頂点rを根として、それを中心としたウニ頂点数maxですか
LCAの条件がちょっとわからんな どうしたらいいんだ
部分木mergeで部分木の葉までの距離 min を取るとなんかよさそう(?)
距離min * children_cnt +1 が解じゃないか
いやmerge演算では部分木の距離をmaxでとる感じかも putVではminね
いやputVでmin取りようがないですやん じゃあ両方保持してまえ
node:={葉までのdistのmax,min,直接のchildren_cnt,答えval}
*///--------------------------------------------------------
int N;
cin>>N;
RerootingDP<node,node,merge,e,put_edge,put_vertex> G(N);
rep(i,0,N-1){
int u,v;
cin>>u>>v;
G.add_edge(u-1,v-1,i,i);
}
// for(auto [a,b,c,d]:G.build(0)) output(a,b,c,d);
G.build();
ll ans=0;
for(auto e:G.reroot()) chmax(ans,e.val);
output(ans);
}