結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
![]() |
提出日時 | 2023-10-03 03:50:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 3,524 bytes |
コンパイル時間 | 1,012 ms |
コンパイル使用メモリ | 113,264 KB |
最終ジャッジ日時 | 2025-02-17 04:04:34 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<cstring>#include<cassert>#include<cmath>#include<ctime>#include<iomanip>#include<numeric>#include<stack>#include<queue>#include<map>#include<set>#include<bitset>#include<random>using namespace std;template<long long MOD>struct Modint{private:unsigned int value;public:constexpr Modint(const long long x = 0) noexcept{long long y = x;if(y < 0 || y >= MOD){y %= MOD;if(y < 0) y += MOD;}value = (unsigned int)y;}constexpr unsigned int &val() noexcept {return value;}constexpr Modint operator+(const Modint &other) noexcept{Modint tmp = *this;return tmp += other;}constexpr Modint operator-(const Modint &other) noexcept{Modint tmp = *this;return tmp -= other;}constexpr Modint operator*(const Modint &other) noexcept{Modint tmp = *this;return tmp *= other;}constexpr Modint operator/(const Modint &other) noexcept{Modint tmp = *this;return tmp /= other;}constexpr Modint &operator+=(const Modint &other) noexcept{value += other.value;if(value >= MOD) value -= MOD;return *this;}constexpr Modint &operator-=(const Modint &other) noexcept{unsigned long long x = value;if(x < other.value) x += MOD;x -= other.value;value = (unsigned int) x;return *this;}constexpr Modint &operator*=(const Modint &other) noexcept{unsigned long long x = value;x *= other.value;value = (unsigned int)(x%MOD);return *this;}constexpr Modint &operator/=(const Modint &other) noexcept{return *this = *this * other.inverse();}constexpr Modint power(long long ex) const noexcept{assert(ex >= 0);Modint p = *this,res = 1;while(ex){if(ex & 1) res *= p;p *= p;ex >>= 1;}return res;}constexpr Modint inverse() const noexcept{assert(value);long long a = value,b = MOD,x = 1,y = 0;while(b){long long q = a/b;a -= q*b; swap(a,b);x -= q*y; swap(x,y);}return Modint(x);}constexpr Modint &operator++(int) noexcept {return *this += 1;}constexpr Modint &operator--(int) noexcept {return *this -= 1;}constexpr bool operator==(const Modint &other){return value == other.value;}constexpr bool operator!=(const Modint &other){return value != other.value;}template<long long mod> friend ostream &operator<<(ostream &os,const Modint<mod> &x);};template<long long mod> ostream &operator<<(ostream &os,const Modint<mod> &x){os << x.value; return os;}//using mint = Modint<998244353>;//using mint = Modint<1000000007>;int N;vector<int> G[1 << 17];int dp[1 << 17][2];void dfs(int u,int p){dp[u][0] = 0,dp[u][1] = 1;for(int v:G[u]) if(v != p){dfs(v,u);dp[u][0] += max(dp[v][0],dp[v][1]);dp[u][1] += max(dp[v][0],dp[v][1]-1);}}void solve(){cin >> N;for(int i = 1;i < N;i++){int u,v;cin >> u >> v;u--; v--;G[u].push_back(v);G[v].push_back(u);}dfs(0,-1);cout << max(dp[0][0],dp[0][1]) << "\n";}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;//cin >> T;while(T--) solve();}