#include #pragma GCC optimize("Ofast") using namespace std; using std::cout; using std::cin; using std::endl; using ll=long long; using ld=long double; ll I=1167167167167167167; ll Q=1e9+7; #define rep(i,a) for (ll i=0;i using _pq = priority_queue, greater>; template ll LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template ll UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}else return 0;} template bool chmax(T &a,const T &b){if(a void So(vector &v) {sort(v.begin(),v.end());} template void Sore(vector &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} template void print_tate(vector &v) {rep(i,v.size()) cout<> tree(ll N){ vector> F(N); for(int i=0;i>a>>b; a--,b--; F[a].push_back(b); F[b].push_back(a); } return F; } vector>> tree_dis(ll N){ vector>> F(N); for(int i=0;i>a>>b>>c; a--,b--; F[a].push_back({b,c}); F[b].push_back({a,c}); } return F; } //ねっこの親は-2に設定しているため、範囲外参照に注意しないと、予期せぬ挙動をします template tuple,vector> tree_dp(vector> G,int nekko){ ll N=G.size(); vector oya(N,-1); oya[nekko]=-2; vector jyun={nekko}; for(int i=0;i>N; int c[N]; vector seen={0}; vector> G(N); rep(i,N-1){ c[i+1]=-1; int a,b; cin>>a>>b; a--,b--; G[a].push_back(b); G[b].push_back(a); } vector order,par; tie(par,order)=tree_dp(G,0); vector dp1(N); vector dp2(N);//used rep(i,N){ int a=order[N-1-i]; ll diff=-1000000; for(auto x:G[a]){ if(x!=par[a]){ chmax(diff,dp1[x]-dp2[x]); } dp1[a]+=dp2[x]; } dp2[a]=max(dp1[a],dp1[a]+diff+1); } cout<