Tranvick

Untitled

Jan 11th, 2012
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.91 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:657772166")
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <cstdlib>
  5. #include <ctime>
  6. #include <cstdio>
  7. #include <algorithm>
  8. #include <cmath>
  9. #include <vector>
  10. #include <set>
  11. #include <stack>
  12. #include <map>
  13. #include <queue>
  14. #include <string>
  15. #include <memory.h>
  16. #include <iterator>
  17. #define mem(A,X) memset(A,X,sizeof(A))
  18. #define memo(A) memset(A,0,sizeof(A))
  19. #define forn(I,B) for (int I=1;I<=(B);I++)
  20. #define forg(H,V) for (int H=first[V];h;h=next[H])
  21. #define rep(I,B) for (int I=0;I<(B);I++)
  22. #define labs(X) (((X)>0)?(X):(-(X)))
  23. #define ropen(X) freopen(X,"r",stdin)
  24. #define wopen(X) freopen(X,"w",stdout)
  25. #define pb push_back
  26. #define mp make_pair
  27. #define all(X) (X).begin(),(X).end()
  28. #define sqr(X) ((X)*(X))
  29.  
  30. using namespace std;
  31.  
  32. typedef pair <int,int> pii;
  33. typedef pair <long long,long long> pll;
  34. typedef double ld;
  35. typedef long long ll;
  36. typedef vector<int> vi;
  37. const int N=111111;
  38. const int INF=111111111;
  39. const double eps=1e-9;
  40. const double pi=3.14159265358979;
  41.  
  42. 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];
  43.  
  44. inline void add(int x,int y){
  45.     ++st[x];++st[y];
  46.     next[++c]=first[x];first[x]=c;es[c]=y;
  47.     swap(x,y);
  48.     next[++c]=first[x];first[x]=c;es[c]=y;
  49. }
  50.  
  51. int be(int x){
  52.     return (x&1)?x+1:x-1;
  53. }
  54.  
  55. void input(){
  56.     ropen("pinetree.in");
  57.     wopen("pinetree.out");
  58.     scanf("%d",&n);
  59.     forn(i,n-1){
  60.         int x,y;
  61.         scanf("%d%d",&x,&y);   
  62.         add(x,y);
  63.     }
  64. }
  65.  
  66. int calc(int x){
  67.     if (f[x]!=-1) return f[x];
  68.     if (st[es[x]]==1) return f[x]=0;
  69.     mx1[x]=-1,mx2[x]=-1;
  70.     for(h[es[x]]=first[es[x]];h[es[x]];h[es[x]]=next[h[es[x]]]){
  71.         if (h[es[x]]==be(x)) continue;
  72.         if (calc(h[es[x]])>mx2[x]) mx2[x]=calc(h[es[x]]);
  73.         if (mx2[x]>mx1[x]) swap(mx2[x],mx1[x]);
  74.     }
  75.     f[x]=max(mx1[x],mx2[x]+1);
  76.     if ((mx1[x]==0 || mx2[x]==0) && f[x]==0) ++f[x];
  77.     return f[x];
  78. }
  79.  
  80. int main(){
  81.     input();
  82.     mem(f,255);
  83.     forn(i,c) if (f[i]==-1) calc(i);
  84.     forn(i,n) if (st[i]==1) ans=min(ans,f[first[i]]);
  85.     printf("%d\n",ans);
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment