Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:657772166")
- #include <iostream>
- #include <iomanip>
- #include <cstdlib>
- #include <ctime>
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <set>
- #include <stack>
- #include <map>
- #include <queue>
- #include <string>
- #include <memory.h>
- #include <iterator>
- #define mem(A,X) memset(A,X,sizeof(A))
- #define memo(A) memset(A,0,sizeof(A))
- #define forn(I,B) for (int I=1;I<=(B);I++)
- #define forg(H,V) for (int H=first[V];h;h=next[H])
- #define rep(I,B) for (int I=0;I<(B);I++)
- #define labs(X) (((X)>0)?(X):(-(X)))
- #define ropen(X) freopen(X,"r",stdin)
- #define wopen(X) freopen(X,"w",stdout)
- #define pb push_back
- #define mp make_pair
- #define all(X) (X).begin(),(X).end()
- #define sqr(X) ((X)*(X))
- using namespace std;
- typedef pair <int,int> pii;
- typedef pair <long long,long long> pll;
- typedef double ld;
- typedef long long ll;
- typedef vector<int> vi;
- const int N=111111;
- const int INF=111111111;
- const double eps=1e-9;
- const double pi=3.14159265358979;
- int es[N+N],first[N],next[N+N],c,n,m,ans=INF,st[N],f[N+N],mx1[N+N],mx2[N+N],h[N];
- inline void add(int x,int y){
- ++st[x];++st[y];
- next[++c]=first[x];first[x]=c;es[c]=y;
- swap(x,y);
- next[++c]=first[x];first[x]=c;es[c]=y;
- }
- int be(int x){
- return (x&1)?x+1:x-1;
- }
- void input(){
- ropen("pinetree.in");
- wopen("pinetree.out");
- scanf("%d",&n);
- forn(i,n-1){
- int x,y;
- scanf("%d%d",&x,&y);
- add(x,y);
- }
- }
- int calc(int x){
- if (f[x]!=-1) return f[x];
- if (st[es[x]]==1) return f[x]=0;
- mx1[x]=-1,mx2[x]=-1;
- for(h[es[x]]=first[es[x]];h[es[x]];h[es[x]]=next[h[es[x]]]){
- if (h[es[x]]==be(x)) continue;
- if (calc(h[es[x]])>mx2[x]) mx2[x]=calc(h[es[x]]);
- if (mx2[x]>mx1[x]) swap(mx2[x],mx1[x]);
- }
- f[x]=max(mx1[x],mx2[x]+1);
- if ((mx1[x]==0 || mx2[x]==0) && f[x]==0) ++f[x];
- return f[x];
- }
- int main(){
- input();
- mem(f,255);
- forn(i,c) if (f[i]==-1) calc(i);
- forn(i,n) if (st[i]==1) ans=min(ans,f[first[i]]);
- printf("%d\n",ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment