結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
![]() |
提出日時 | 2020-05-05 15:15:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 7,154 bytes |
コンパイル時間 | 2,025 ms |
コンパイル使用メモリ | 181,520 KB |
実行使用メモリ | 22,016 KB |
最終ジャッジ日時 | 2024-06-26 10:17:58 |
合計ジャッジ時間 | 4,029 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
コンパイルメッセージ
main.cpp:249:55: warning: friend declaration 'std::ostream& operator<<(std::ostream&, const Matrix<Z>::mat&)' declares a non-template function [-Wnon-template-friend] 249 | friend ostream& operator<<(ostream &os, const mat &A); | ^ main.cpp:249:55: note: (if this is not what you intended, make sure the function template has already been declared and add '<>' after the function name here)
ソースコード
#include <bits/stdc++.h>#include <algorithm>#include <cmath>#include <set>#include <cstdio>#include <vector>#include <iostream>#include <utility>#include <queue>#include <map>#include <complex>#define fir first#define sec second#define sz(s) (s).size()#define pb push_back#define get(n) scanf("%d",&n);#define gets(s) string s;cin >> (s);#define prfi(n) printf("%d", &n);#define prfd(n) printf("%lf", &n);#define All(s) (s).begin(), (s).end()#define rep(i,j) for(int (i)=0;(i)<(j);(i)++)#define For(i,j,k) for(int (i)=(j);(i)<(k);(i)++)#define drep(i,j) for(int (i)=(j);(i)>=0;(i)--)#define Ford(i,j,k) for(int (i)=(j);i>=(k);i--)#define fore(c,v) for(auto (c): (v))#define lp for(int __=0;__<n;i++)#define mem(a,b) memset(a,b,sizeof(a));#define dump(x) std::cout << #x << " = " << (x) << std::endl;#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;using ull = unsigned long long int;using ll = long long;using ld = long double;using pii = std::pair<int,int>;using pll = std::pair<ll, ll>;using vi = std::vector<int> ;using vvi = std::vector<vi> ;using vll = std::vector<ll>;using vvll = std::vector<vll>;using vd = std::vector<double> ;using vvd = std::vector<vd> ;using qi = std::queue<int> ;using vpii = std::vector<std::pair<int, int> >;using vpll = std::vector<pll>;using namespace std;const int Mod = (1e9) + 7;const int INF = 1e9 + 19;const ll INFL = 1e18 + 19;const int dx[] = {-1, 0, 0, 1};const int dy[] = {0, -1, 1, 0};const int dx2[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};const int dy2[] = {1, 0, -1, 1, 0, -1, 1, 0, -1};const double EPS = 1e-10;//_____________________________________Templates_________________________________________//template<class T1, class T2> inline void chmin(T1 &a, T2 b){if(a > b) a = b;}template<class T1, class T2> inline void chmax(T1 &a, T2 b){if(a < b) a = b;}template<class T> inline void pri(T a){cout << a << endl;}template<class Z> using vec = vector<Z>;template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;//mainly use for dynamic progtemplate<class T1, class T2>void update(T1 &a, T2 b){a += b;if(a > Mod) a %= Mod;}inline void IN(void){return;}template <typename First, typename... Rest>void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}inline void OUT(void){cout << "\n";return;}template <typename First, typename... Rest>void OUT(First first, Rest... rest){cout << first << " ";OUT(rest...);return;}bool pairsort(pll pl, pll pr){if(pl.first == pr.first)return pl.second > pr.second;return pl.first < pr.first;}int cntbit(ll a,int n,int j){int res = 0;For(i,j,n){if(a>>i & 1){res++;}}return res;}vector<int> make_bit(int a){vector<int> res; for(int i=31;i>=0;i--)if(a&(1<<i))res.pb(i);return res;}bool stdbit(int a, int b){return a&(1 << b); }int GCD(int a, int b){if(b > a)return GCD(b,a);if(a%b == 0)return b;else return GCD(b, a%b);}int LCM(int a, int b){return a*b/GCD(a,b);}int roundup(int a, int b){if(a % b == 0)return a/b;else return (a+b)/b;}int rounddown(int a, int b){if(a%b == 0)return a/b;else {return (a-b)/b;}}ll pow(ll a, ll n){ll res = 1;while(n > 0){if(n&1)res *= a; a *= a; n = n >> 1;}return res;}ll GetDiviserCount(ll N)//約数の個数{ll res = 1;For(i,2,sqrt(N)+1){ll cnt = 0;while(N%i == 0){cnt++;N /= i;}res *= (cnt + 1);if(N == 1)break;}if(N != 1)res *= 2;return res;}vll GetDivisor(ll N)//約数列挙{vll res;for(ll i = 1;i*i <= N;i++){if(N%i == 0){res.pb(i);if(i*i != N)res.pb(N/i);}}sort(All(res));return res;}struct mint {ll x; // typedef long long ll;mint(ll x=0):x((x%Mod+Mod)%Mod){}mint operator-() const { return mint(-x);}mint& operator+=(const mint a) {if ((x += a.x) >= Mod) x -= Mod;return *this;}mint& operator-=(const mint a) {if ((x += Mod-a.x) >= Mod) x -= Mod;return *this;}mint& operator*=(const mint a) {(x *= a.x) %= Mod;return *this;}mint operator+(const mint a) const {mint res(*this);return res+=a;}mint operator-(const mint a) const {mint res(*this);return res-=a;}mint operator*(const mint a) const {mint res(*this);return res*=a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}// for prime modmint inv() const {return pow(Mod-2);}mint& operator/=(const mint a) {return (*this) *= a.inv();}mint operator/(const mint a) const {mint res(*this);return res/=a;}friend ostream& operator<<(ostream& os, const mint& a);};ostream& operator<<(ostream& os, const mint& a){os << a.x;return os;}struct combination {vector<mint> fact, ifact;combination(int n):fact(n+1),ifact(n+1) {assert(n < Mod);fact[0] = 1;for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;ifact[n] = fact[n].inv();for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;}mint operator()(int n, int k) {if (k < 0 || k > n) return 0;return fact[n]*ifact[k]*ifact[n-k];}};template<class Z>struct Matrix{using mat = Matrix<Z>;vector<vector<Z>> m_dat;int m_h;int m_w;Matrix(int h, int w) : m_h(h), m_w(w) ,m_dat(h,vector<Z>(w)) {}vector<Z> &operator[] (int idx){return m_dat[idx];}mat Multiple(mat &a){mat C(m_h, a.m_w);for(int i=0;i<m_h;i++){for(int j=0;j<a.m_w;j++){for(int k=0;k<m_w;k++){C[i][j] += m_dat[i][k] * a[k][j];}}}return C;}mat Pow(ll x){mat B(m_h,m_w);for(int i=0;i<m_h;i++){B[i][i] = 1;}mat A = *this;while(x > 0){if(x&1)B = B.Multiple(A);A = A.Multiple(A);x = x >> 1;}return B;}friend ostream& operator<<(ostream &os, const mat &A);};template<class Z>ostream& operator<<(ostream &os, Matrix<Z>& A){for(int i=0;i<A.m_h;i++){for(int j=0;j<A.m_w;j++){os << A[i][j] << " ";}os << endl;}return os;}template<class T>using mat = Matrix<T>;//_____________________ following sorce code_________________________//const int max_n = 3 * (1e5) + 1;const int max_m = 83 * (1e5) + 1;int n,m,k;ll N;int h,w;vvi tree;string S;int a,b,c;vi v;int ans;double x,y,z;vector<int> G[101010];vvi dp;void dfs(int v,int u=-1){dp[v][1] = 1;dp[v][0] = 0;int res = 0;fore(e, G[v]){if(u == e)continue;dfs(e,v);dp[v][1] += max(dp[e][1]-1, dp[e][0]);dp[v][0] += max(dp[e][0], dp[e][1]);}}signed main (int argc, char* argv[]) {cin.tie(0);ios::sync_with_stdio(false);IN(n);rep(i,n-1){IN(a,b);a--;b--;G[a].pb(b);G[b].push_back(a);}dp = vvi(n,vi(2));dfs(0);ans = max(dp[0][1], dp[0][0]);cout << ans <<endl;//for(auto c : ans){cout << c << endl;}//cout << fixed << setprecision(15) << ans << endl;return 0;}