結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
|
提出日時 | 2023-05-09 21:31:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 123 ms / 2,000 ms |
コード長 | 21,632 bytes |
コンパイル時間 | 2,778 ms |
コンパイル使用メモリ | 218,592 KB |
実行使用メモリ | 50,688 KB |
最終ジャッジ日時 | 2024-11-26 06:51:51 |
合計ジャッジ時間 | 6,335 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
/*Hi,I am warabi.Welcome to my coding space.Let me give you a great word of advice."The pen is mightier than the sword"-by Edward Bulwer-Lytton_,,....,,_ _人人人人人人人人人人人人人人人人人人_-''":::::::::::::`''> ゆっくりできるとでも? <ヽ::::::::::::::::::::: ̄^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y ̄|::::::;ノ´ ̄\:::::::::::\_,. -‐ァ __ _____ ______|::::ノ ヽ、ヽr-r'"´ (.__ ,´ _,, '-´ ̄ ̄`-ゝ 、_ イ、_,.!イ_ _,.ヘーァ'二ハ二ヽ、へ,_7 'r ´ ヽ、ン、::::::rー''7コ-‐'"´ ; ', `ヽ/`7 ,'==─- -─==', ir-'ァ'"´/ /! ハ ハ ! iヾ_ノ i イ iゝ、イ人レ/_ルヽイ i |!イ´ ,' | /__,.!/ V 、!__ハ ,' ,ゝ レリイi (ヒ_] ヒ_ン ).| .|、i .||`! !/レi' (ヒ_] ヒ_ン レ'i ノ !Y!"" ,___, "" 「 !ノ i |,' ノ !'" ,___, "' i .レ' L.',. ヽ _ン L」 ノ| .|( ,ハ ヽ _ン 人! | ||ヽ、 ,イ| ||イ| /,.ヘ,)、 )>,、 _____, ,.イ ハ レ ル` ー--─ ´ルレ レ´Take your time.GIVE ME AC!!!!!!!!!!!!!!!!!!!!!!!!!*/#include <bits/stdc++.h>using namespace std;#define ll long long#define ld long double#define V vector#define rep(i,a,b) for(ll i=a;i<b;i++)#define brep(i,a,b) for(ll i=a;i>=b;i--)#define reph(i,vec) for(auto &i:vec)#define FI first#define SE second#define P pair#define PB push_back#define EB emplace_back#define INS insert#define all(vec) vec.begin(),vec.end()#define in(name) ll name;cin >> name#define ins(name) string name;cin >> name;#define inc(name) char name;cin >> name#define ing(name,size,E) vector<vector<ll>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);name[b].PB(a);}#define ing_on(name,size,E) vector<vector<long long>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);}#define ing_cost(name,size,E) vector<vector<P<ll,ll>>> name(size);rep(i,0,E){in(a);in(b);in(c);a--;b--;name[a].PB({b,c});name[b].PB({a,c});}#define invll(name,size) vector<ll> name(size);reph(i,name)cin >> i#define invvll(name,size1,size2) vector<vector<long long>> name(size1,vector<long long>(size2));reph(v,name)reph(i,v)cin>>i;#define invp(name,size) vector<P<ll,ll>> name(size);for(ll i=0;i<size;i++)cin >> name[i].FI >> name[i].SE#define out(n) cout << (n) << endl#define _out(n) cout << " " << (n) << endl;#define notout(n) cout << (n)#define out_(n) cout << (n) << " "#define set_out(n,k) cout << fixed << setprecision(k) << (n) << endl;#define set_notout(n,k) cout << fixed << setprecision(k) << (n) << endl;#define set_out_(n,k) cout << fixed << setprecision(k) << (n) << " ";#define vout(vec) for(int i=0;i<vec.size();i++)cout<<(i?" ":"")<<(vec[i]);cout<<endl;#define nel cout<<endl;#define getbit(n,k) (((1LL<<(k))&(n))>0)#define INF 1000000000000000000#define MOD 1000000007#define MOD2 998244353#define CMOD MOD2#define EPS 0.00000001//debug#define bug assert(false);#define debug cout<<"OK Line "<<__LINE__<<endl;////constexpr long double PI=3.14159265358979323846;//templatetemplate<typename T>inline bool chmax(T &a,const T b){if(a<b){a=b;return true;}return false;}template<typename T>inline bool chmin(T &a,const T b){if(a>b){a=b;return true;}return false;}//namespace Warabi{//常備変数のコーナーV<bool> primes(3001000,true);V<ll> prime_list;V<ll> prime_rui(3001000,0LL);V<bool> visiteded(300100);V<bool> afed(300100,false);V<ll> k1(200100,0ll);V<ll> k2(200100,0ll);////常備構造体宣言のコーナーclass UnionFind {private:ll NumberOfElements;ll Not1NumberOfelements;public:vector<ll> par;vector<ll> SIZE;void init(ll sz) {par.resize(sz, -1LL);SIZE.resize(sz,1LL);NumberOfElements=sz;Not1NumberOfelements=0ll;}ll root(ll pos) {if (par[pos] == -1) return pos;par[pos] = root(par[pos]);return par[pos];}bool same(ll u, ll v) {if (root(u) == root(v)) return true;return false;}ll SZ(ll u){return SIZE[root(u)];}ll noe(){return NumberOfElements;}ll nnoe(){return Not1NumberOfelements;}bool unite(ll u, ll v) {u = root(u); v = root(v);if (u == v){return false;}if(SZ(u) == 1LL and SZ(v) == 1LL)Not1NumberOfelements++;if(u<v)swap(u,v);par[u] = v;SIZE[v] += SIZE[u];NumberOfElements--;return true;}};class SCC{public:V<V<ll>> G;V<V<ll>> UG;V<ll> order;V<ll> GROUP;V<bool> visited;V<ll> groupsize;void init(ll sz){G.resize(sz,V<ll>(0));UG.resize(sz,V<ll>(0));GROUP.resize(sz,-1ll);visited.resize(sz,false);return;}void dfs(ll now){visited[now]=true;reph(i,G[now]){if(visited[i])continue;dfs(i);}order.PB(now);return;}void dfs2(ll now,ll group){GROUP[now]=group;reph(i,UG[now]){if(GROUP[i]!=-1ll and GROUP[i]!=group)continue;if(GROUP[i]!=-1ll)continue;dfs2(i,group);}return;}void make_group(V<V<ll>> Graph_function){G=Graph_function;rep(i,0,(ll)G.size()){reph(j,G[i]){UG[j].PB(i);}}rep(i,0,(ll)G.size()){if(visited[i])continue;dfs(i);}reverse(all(order));ll now_group=0LL;reph(i,order){if(GROUP[i]!=-1)continue;dfs2(i,now_group);now_group++;}groupsize.resize(now_group,0ll);rep(i,0,(ll)G.size())groupsize[GROUP[i]]++;return;}};template<typename X,typename M>class SegmentTree{public:long long sz;using FX=function<X(X,X)>;using FA=function<X(X,M)>;using FM=function<M(M,M)>;const FX fx;const FA fa;const FM fm;const X ex;const M em;vector<X> node;vector<M> lazy;SegmentTree(long long sz_,FX fx_,FA fa_,FM fm_,X ex_,M em_):sz(),fx(fx_),fa(fa_),fm(fm_),ex(ex_),em(em_){long long n=1LL;while(n<sz_)n*=2;sz=n;node.resize(sz*2-1,ex);lazy.resize(sz*2-1,em);}void set(long long index,X x){node[index+sz-1]=x;return;}void build(){for(int i=sz-2;i>=0;i--)node[i]=fx(node[i*2+1],node[i*2+2]);return;}void eval(long long k){if(lazy[k]==em)return;if(k<sz-1){lazy[k*2+1]=fm(lazy[k*2+1],lazy[k]);lazy[k*2+2]=fm(lazy[k*2+2],lazy[k]);}node[k]=fa(node[k],lazy[k]);lazy[k]=em;}void update_sub(long long a,long long b,M x,long long k,long long l,long long r){//cout << " " << a << " " << b << " " << l << " " << r << endl;eval(k);if(a<=l and r<=b){lazy[k]=fm(lazy[k],x);//cout<<" "<<lazy[k]<<endl;eval(k);return;}else if(a<r and l<b){update_sub(a,b,x,k*2+1,l,(l+r)/2);update_sub(a,b,x,k*2+2,(l+r)/2,r);node[k]=fx(node[k*2+1],node[k*2+2]);return;}return;}void update(long long a,long long b,M x){update_sub(a,b,x,0LL,0LL,sz);return;}void add_sub(long long a,X x,long long k,long long l,long long r){eval(k);node[k]+=x;if(k<sz-1){long long mid=(l+r)/2;if(a<mid)add_sub(a,x,k*2+1,l,mid);else add_sub(a,x,k*2+2,mid,r);}return;}void add(long long a,X x){add_sub(a,x,0LL,0LL,sz);}X query_sub(long long a,long long b,long long k,long long l,long long r){eval(k);if(r<=a or b<=l)return ex;else if(a<=l and r<=b)return node[k];else{X Xl=query_sub(a,b,k*2+1,l,(l+r)/2);X Xr=query_sub(a,b,k*2+2,(l+r)/2,r);//cout<<" / "<<Xl<<" "<<Xr<<endl;return fx(Xl,Xr);}}X query(long long a,long long b){return query_sub(a,b,0LL,0LL,sz);}inline X operator [] (long long index){return query(index,index+1);}};template<typename T>class multimap{private:map<T,ll> mp;public:void add(ll x){mp[x]++;return;}void del(ll x){mp[x]--;if(mp[x]<1)mp.erase(x);return;}T maximum(){return mp.rbegin()->first;}T minimum(){return mp.begin()->first;}};class LCA{public:vector<vector<long long>> parent;vector<long long> dist;vector<vector<long long>> G;LCA(const vector<vector<long long>> &gr){init(gr);}void dfs(long long v,long long p,long long d){parent[0][v]=p;dist[v]=d;for(long long next : G[v]){if(next==p)continue;dfs(next,v,d+1);}return;}void init(const vector<vector<long long>> &gr){G=gr;parent.assign(33,vector<long long>(G.size(),-1LL));dist.assign(G.size(),-1LL);dfs(0LL,-1LL,0LL);for(int i=0;i<32;i++){for(int j=0;j<(int)G.size();j++){if(parent[i][j]<0LL){parent[i+1][j]=-1LL;}else{parent[i+1][j]=parent[i][parent[i][j]];}}}return;}long long lca(long long u,long long v){if(dist[u]<dist[v])swap(u,v);long long between=dist[u]-dist[v];for(int i=0;i<33;i++){if(between&(1LL<<i)){u=parent[i][u];}}if(u==v)return u;for(int i=32;i>=0;i--){if(parent[i][u]!=parent[i][v]){u=parent[i][u];v=parent[i][v];}}assert(parent[0][u]==parent[0][v]);return parent[0][u];}long long get_dist(long long u,long long v){return dist[u]+dist[v]-2*dist[lca(u,v)];}bool on_path(long long u,long long v,long long a){return get_dist(u,v)==get_dist(u,a)+get_dist(v,a);}};class nCk {public:const long long m;const long long MAXIMUM = 1000000;vector<long long> fac, facinv, inv;nCk(long long m_);~nCk();long long com(long long n, long long k)const;};nCk::nCk(long long m_):m(m_) {fac.resize(MAXIMUM + 3);facinv.resize(MAXIMUM + 3);inv.resize(MAXIMUM + 3);fac[0] = fac[1] = 1;facinv[0] = facinv[1] = 1;inv[1] = 1;for (long long i = 2; i < MAXIMUM + 2; i++) {fac[i] = fac[i - 1] * i % m;inv[i] = m - inv[m % i] * (m / i) % m;facinv[i] = facinv[i - 1] * inv[i] % m;}}nCk::~nCk(){}long long nCk::com(long long n, long long k)const {if(k==0)return 1;if (n < k)return 0LL;assert(!(n < 0 || k < 0));return fac[n] * (facinv[k] * facinv[n - k] % m) % m;}////常備構造体宣言のコーナーstruct STC{ll s,t,cost;};////常備関数のコーナーvoid Yes(bool f){cout<<(f?"Yes":"No")<<endl;}void YES(bool f){cout<<(f?"YES":"NO")<<endl;}//木の直径を求めるSTC Cdiameter(V<V<P<ll,ll>>> G,ll start,bool type){visiteded=afed;queue<ll> sirabe;sirabe.push(start);V<ll> short_load(G.size(),0LL);while(!sirabe.empty()){ll s=sirabe.front();sirabe.pop();visiteded[s]=true;reph(i,G[s]){if(visiteded[i.FI])continue;short_load[i.FI]=short_load[s]+i.SE;sirabe.push(i.FI);}}ll far_max=-1LL;ll element=-1LL;rep(i,0,(ll)G.size()){if(far_max>=short_load[i])continue;far_max=short_load[i];element=i;}if(type)return Cdiameter(G,element,false);else return {start,element,far_max};}//素数の取得void prime_init(){V<bool> at(3001000,true);primes=at;primes[0]=primes[1]=false;rep(i,2,3000100){if(!primes[i])continue;for(ll j=i*2;j<=300100;j+=i)primes[j]=false;}rep(i,1,3000100){if(primes[i]){prime_list.PB(i);prime_rui[i]=prime_rui[i-1]+1;}else{prime_rui[i]=prime_rui[i-1];}}return;}//modpowlong long modpow(long long a, long long b, long long m) {long long p = 1, q = a;for (int i = 0; i < 63; i++) {if ((b & (1LL << i)) != 0) {p *= q;p %= m;}q *= q;q %= m;}return p;}//逆元long long Div(long long a, long long b, long long m) {return (a * modpow(b, m - 2, m)) % m;}//点と点の距離を返すlong double Dis(ll ax,ll ay,ll bx,ll by){return sqrt(pow(ax-bx,2)+pow(ay-by,2));}//二つのベクトルから平行四辺形の面積を返すll he(ll x0,ll y0,ll x1,ll y1,ll x2,ll y2){//外積を二で割るreturn abs((x1-x0)*(y2-y0)-(x2-x0)*(y1-y0));}//template<typename T>ll Lis_size(V<T> arr,ll sz){const T TINF=numeric_limits<T>::max();V<T> DP(sz+1,TINF);DP[0]=-TINF;rep(i,0,sz){*lower_bound(all(DP),arr[i])=arr[i];}ll ans=0LL;rep(i,1,sz+1){if(DP[i]!=TINF)ans=i;}return ans;}string toBinary(ll n){string r;while (n != 0LL){r += ( n % 2LL == 0LL ? "0" : "1" );n /= 2LL;}return r;}template<typename T>V<ll> press(V<T> arr){V<T> X=arr;sort(all(X));X.erase(unique(all(X)),X.end());V<ll> ans(arr.size());rep(i,0LL,(ll)arr.size()){ans[i]=lower_bound(all(X),arr[i])-X.begin();}return ans;}P<V<V<ll>>,V<V<P<ll,ll>>>> warshall_floyd(ll N,V<V<P<ll,ll>>> G){V<V<ll>> DP(N,V<ll>(N,INF));rep(i,0,N)DP[i][i]=0LL;V<V<P<ll,ll>>> prev(N,V<P<ll,ll>>(N,{INF,INF}));rep(i,0,N){reph(j,G[i]){DP[i][j.FI]=j.SE;prev[i][j.FI]={i,j.FI};}}rep(k,0,N){rep(i,0,N){rep(j,0,N){if(chmin(DP[i][j],DP[i][k]+DP[k][j])){prev[i][j]=prev[k][j];}}}}return {DP,prev};}template<typename T>void to_sum(V<T> &arr){rep(i,0,(ll)arr.size()-1LL){arr[i+1]+=arr[i];}return;}template<typename T>void including_map(ll H,ll W,V<V<T>> &G,T c){V<V<T>> new_G(H+2,V<T>(W+2));rep(i,0,W+2)new_G[0][i]=c;rep(i,1,H+1){new_G[i][0]=c;new_G[i][W+1]=c;rep(j,1,W+1){new_G[i][j]=G[i-1][j-1];}}rep(i,0,W+2)new_G[H+1][i]=c;G=new_G;return;}struct BIT {private:vector<int> bit;int N;public:BIT(int size) {N = size;bit.resize(N + 1);}// 一点更新ですvoid add(int a, int w) {for (int x = a; x <= N; x += x & -x) bit[x] += w;}// 1~Nまでの和を求める。int sum(int a) {int ret = 0;for (int x = a; x > 0; x -= x & -x) ret += bit[x];return ret;}};ll fall_down(ll n,const V<ll> &v){ll ans = 0;BIT b(n); // これまでの数字がどんな風になってるのかをメモる為のBITfor (int i = 0; i < n; i++) {ans += i - b.sum(v[i]); // BITの総和 - 自分より左側 = 自分より右側b.add(v[i], 1); // 自分の位置に1を足す}return ans;}set<ll> factor(ll N){set<ll> ans;for(ll i=1LL;i*i<=N;i++){if(N%i)continue;ans.INS(i);ans.INS(N/i);}return ans;}V<ll> dijkstra(ll sz,V<V<P<ll,ll>>> G,ll s){V<ll> ans(sz,INF);ans[s]=0LL;priority_queue<P<ll,ll>,vector<P<ll,ll>>,greater<P<ll,ll>>> examine;examine.push({0LL,s});while(examine.size()){P<ll,ll> p=examine.top();examine.pop();ll now=p.SE,dist=p.FI;if(ans[now]<dist)continue;reph(i,G[now]){ll next=i.FI,c=i.SE;if(chmin(ans[next],dist+c)){examine.push({dist+c,next});}}}return ans;}set<ll> pass(const V<V<ll>> &G,ll s,ll t){V<bool> visited(G.size(),false);set<ll> ans,res;function<void(ll)> dfs=[&](ll now){visited[now]=true;res.INS(now);if(now==t){ans=res;}reph(next,G[now]){if(visited[next])continue;dfs(next);}res.erase(now);return;};dfs(s);return ans;}// 負の数にも対応した mod (a = -11 とかでも OK)inline long long mod(long long a, long long m) {long long res = a % m;if (res < 0) res += m;return res;}// 拡張 Euclid の互除法long long extGCD(long long a, long long b, long long &p, long long &q) {if (b == 0) { p = 1; q = 0; return a; }long long d = extGCD(b, a%b, q, p);q -= a/b * p;return d;}long long extGcd(long long a, long long b, long long &p, long long &q) {if (b == 0) { p = 1; q = 0; return a; }long long d = extGcd(b, a%b, q, p);q -= a/b * p;return d;}// 逆元計算 (ここでは a と m が互いに素であることが必要)long long modinv(long long a, long long m) {long long x, y;extGCD(a, m, x, y);return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので}// Garner のアルゴリズム, x%MOD, LCM%MOD を求める (m は互いに素でなければならない)// for each step, we solve "coeffs[k] * t[k] + constants[k] = b[k] (mod. m[k])"// coeffs[k] = m[0]m[1]...m[k-1]// constants[k] = t[0] + t[1]m[0] + ... + t[k-1]m[0]m[1]...m[k-2]long long Garner(vector<long long> b, vector<long long> m, long long Mmod) {m.push_back(Mmod); // banpeivector<long long> coeffs((int)m.size(), 1);vector<long long> constants((int)m.size(), 0);for (int k = 0; k < (int)b.size(); ++k) {long long t = mod((b[k] - constants[k]) * modinv(coeffs[k], m[k]), m[k]);for (int i = k+1; i < (int)m.size(); ++i) {(constants[i] += t * coeffs[i]) %= m[i];(coeffs[i] *= m[k]) %= m[i];}}return constants.back();}pair<long long, long long> ChineseRem(const vector<long long> &b, const vector<long long> &m) {long long r = 0, M = 1;for (int i = 0; i < (int)b.size(); ++i) {long long p, q;long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d)if ((b[i] - r) % d != 0) return make_pair(0, -1);long long tmp = (b[i] - r) / d * p % (m[i]/d);r += M * tmp;M *= m[i]/d;}return make_pair(mod(r, M), M);}map<ll,ll> bunkai(ll n){map<ll,ll> ans;ll Nn=n;for(int i=2;i*i<=Nn;i++){while(n%i==0){n/=i;ans[i]++;}}if(n>1){ans[n]++;}return ans;}template<typename T>void RLE(vector<T> &arr){vector<T> res;res.push_back(arr[0]);for(const T t:arr){if(res.back()!=t)res.push_back(t);}arr=res;return;}template<typename T>vector<pair<T,long long>> RLE(vector<T> arr){vector<pair<T,long long>> res;res.emplase_back(arr[0]);for(const T t:arr){if(res.back()!=t)res.emplase_back(t,1ll);else res.back().second++;}return res;}vector<pair<long long,long long>> EulerTour(const vector<vector<long long>> &G){long long N=(long long)G.size();vector<pair<long long,long long>> res(N);long long now=0ll;function<void(long long,long long)> dfs=[&](long long v,long long p){res[v].first=now;++now;for(const long long next:G[v]){if(next==p)continue;dfs(next,v);}res[v].second=now;++now;return;};dfs(0,-1ll);return res;}}namespace Guest{};////構造体宣言のコーナーstruct P2{ll l,r;};bool operator < (P2 a,P2 b){if(a.r<b.r)return true;if(a.r==b.r and a.l<b.l)return true;return false;}long long gcd(long long a,long long b){if(b==0LL)return a;return gcd(b,a%b);}long long lcm(long long a,long long b){return a*b/gcd(a,b);}long long mpow(long long a,long long b){long long res=1ll;for(long long i=0;i<b;i++)res*=a;return res;}signed main(){/*文章を読み落としていませんか?制約も隅々まで読んでいますか?注意・セグ木のupdate関数はl,rの値を渡したときにl以上r未満の区間だからご注意をrは含みません・BITって1-indexedなんだぜイケてるよな・転倒数求める関数、0を含んでると使えないらしいぜ・using namespace Warabi??*///using namespace Warabi;in(N);ing(G,N,N-1);V<V<ll>> DP(N,V<ll>(2,0ll));function<void(ll,ll)> dfs=[&](ll v,ll p){if(G[v].size()==1 and v){DP[v][1]=1ll;return;}ll sum=0ll;reph(next,G[v]){if(p==next)continue;dfs(next,v);DP[v][0]+=max(DP[next][0],DP[next][1]);DP[v][1]+=max(DP[next][0],DP[next][1]);sum+=DP[next][0];}chmax(DP[v][1],sum+1);return;};dfs(0,-1);out(max(DP[0][0],DP[0][1]));}