結果

問題 No.1752 Up-Down Tree
ユーザー riano
提出日時 2021-10-11 23:29:49
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 4,737 bytes
コンパイル時間 2,625 ms
コンパイル使用メモリ 204,588 KB
最終ジャッジ日時 2025-01-25 00:12:19
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 12 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Pr pair<ll,ll>
#define Tp tuple<int,int,int>
#define all(v) v.begin(),v.end()
#define riano_ std::ios::sync_with_stdio(false);std::cin.tie(nullptr);typedef modint<mod> mint
using Graph = vector<vector<ll>>;
const ll mod = 998244353;
template<uint64_t mod>
struct modint{
uint64_t val;
constexpr modint(const int64_t val_=0) noexcept:val((val_%int64_t(mod)+int64_t(mod))%int64_t(mod)){}
constexpr modint operator-() const noexcept{
return modint(*this)=mod-val;
}
constexpr modint operator+(const modint rhs) const noexcept{
return modint(*this)+=rhs;
}
constexpr modint operator-(const modint rhs) const noexcept{
return modint(*this)-=rhs;
}
constexpr modint operator*(const modint rhs) const noexcept{
return modint(*this)*=rhs;
}
constexpr modint operator/(const modint rhs) const noexcept{
return modint(*this)/=rhs;
}
constexpr modint &operator+=(const modint rhs) noexcept{
val+=rhs.val;
val-=((val>=mod)?mod:0);
return (*this);
}
constexpr modint &operator-=(const modint rhs) noexcept{
val+=((val<rhs.val)?mod:0);
val-=rhs.val;
return (*this);
}
constexpr modint &operator*=(const modint rhs) noexcept{
val=val*rhs.val%mod;
return (*this);
}
constexpr modint &operator/=(modint rhs) noexcept{
uint64_t ex=mod-2;
modint now=1;
while(ex){
now*=((ex&1)?rhs:1);
rhs*=rhs,ex>>=1;
}
return (*this)*=now;
}
constexpr bool operator==(const modint rhs) noexcept{
return val==rhs.val;
}
constexpr bool operator!=(const modint rhs) noexcept{
return val!=rhs.val;
}
friend constexpr ostream &operator<<(ostream& os,const modint x) noexcept{
return os<<(x.val);
}
friend constexpr istream &operator>>(istream& is,modint& x) noexcept{
uint64_t t;
is>>t,x=t;
return is;
}
};
//segment tree
//1-indexed all
class segtree {
public:
ll n;
vector<ll> A;
segtree(ll k){
n = 1;
while(n<k){ n *= 2; }
A=vector<ll>(2*n,0);
}
//a[i]x
void add(ll i,ll x){
int index = n-1+i;
A[index] += x;
while(index>1){
index /= 2;
A[index] = max(A[2*index],A[2*index+1]);
}
}
//a[i]
void replace(ll i,ll x){
int index = n-1+i;
A[index] = x;
while(index>1){
index /= 2;
A[index] = max(A[2*index],A[2*index+1]);
}
}
//a[i]+a[i+1]+…+a[j]
ll mx(ll i,ll j){
return rangesum(i,j,1,1,n);
}
// a,b k c,d(k=1,c=1,d=n)
ll rangesum(ll a,ll b,ll k,ll c,ll d){
//
ll el = 0;
if(d<a||b<c){
return el;
}
else if(a<=c&&d<=b){
return A[k];
}
else{
//2
ll p = max(rangesum(a,b,k*2,c,(c+d)/2),rangesum(a,b,k*2+1,(c+d)/2+1,d));
return p;
}
}
};
segtree seq(200001);
ll base = 1e6; //maxindex val*base+index
//dfs
//s: i:dfs t:
vector<int> vis; int t;
vector<Pr> euler_time;
void dfs(Graph &G, int s,int i){
t++;
ll st = t;
for(int nx:G[s]){
if(vis[nx]==i) continue;
vis[nx] = i;
dfs(G,nx,i);
}
t++;
ll en = t;
euler_time[s] = make_pair(st,en);
ll m1 = seq.mx(st,en);
ll m1_val = m1/base; ll m1_idx = m1%base;
seq.replace(m1_idx,0);
ll m2 = seq.mx(st,en);
ll m2_val = m2/base; ll m2_idx = m2%base;
seq.replace(m2_idx,0);
if(m1_val%2==0&&m2_val&2==0){
m2_val--;
seq.replace(m2_idx,base+m2_idx);
}
seq.replace(st,(m1_val+m2_val+1)*base+st);
}
void dfs_dp(Graph &G, int s,int i){
for(int nx:G[s]){
if(vis[nx]==i) continue;
vis[nx] = i;
dfs_dp(G,nx,i);
}
auto[st,en] = euler_time[s];
}
int main() {
riano_; ll ans = 0;
ll N; cin >> N;
Graph G(N+1);
rep(i,N-1){
ll a,b; cin >> a >> b;
G[a].push_back(b); G[b].push_back(a);
}
//main
vis.assign(N+1,-1);
euler_time.assign(N+1,make_pair(0,0));
int s = 1;
vis[s] = 0; t = 0; //s:
dfs(G,s,0); //s:
vis[s] = 1;
dfs_dp(G,s,1);
ans = seq.mx(1,2*N)/base;
cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0