daily pastebin goal
56%
SHARE
TWEET

two paths

a guest Mar 25th, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define sz(x) ((int)(x).size())
  3. #define endl '\n'
  4. #define debug(X) cout << #X << " = " << X << endl
  5. #define rep(i,a,b) for(int(i)=(a);(i)<(b);i++)
  6. #define SZ(v) (int)v.size()
  7.  
  8. using namespace std;
  9. typedef long long ll;
  10. const int mod = (int) 1e9 + 7;
  11. const int oo = (int) 1e9;
  12.  
  13. const int N = 1e5 + 2, E = 2e5 + 3;
  14.  
  15. int n, m, e;
  16. int src, dst;
  17. int head[N], nxt[E], to[E];
  18.  
  19. int longest_path[E][2], res[E];
  20.  
  21. /* fast input */
  22. char buf[1<<24],*w=buf;
  23. int getint(){
  24.  while(!isdigit(*w))w++;
  25.  int r = 0;
  26.  while(isdigit(*w)){
  27.    r = r * 10 + *w - '0';
  28.    w++;
  29.  }
  30.  return r;
  31. }
  32.  
  33. void init()
  34. {
  35.     e = 0;
  36.     memset(head,-1,sizeof(head));
  37.     memset(res,-1,sizeof(res));
  38. }
  39.  
  40. void addEdge(int f, int t)
  41. {
  42.     nxt[e] = head[f];
  43.     head[f] = e;
  44.     to[e++] = t;
  45. }
  46.  
  47. void addBiEdge(int a, int b)
  48. {
  49.     addEdge(a, b);
  50.     addEdge(b, a);
  51. }
  52.  
  53. int solve(int u, int p, int idx)
  54. {
  55.     if(~res[idx])return res[idx];
  56.     int ans = 0;
  57.     for(int k=head[u]; ~k; k=nxt[k]){
  58.         int v = to[k];
  59.         if(v==p) continue;
  60.         int tmp = solve(v,u,k);
  61.         longest_path[idx][0] = max(longest_path[idx][0], longest_path[k][1]+1);
  62.         if(longest_path[idx][0] > longest_path[idx][1])
  63.             swap(longest_path[idx][0], longest_path[idx][1]);
  64.         ans = max(tmp, ans);
  65.     }
  66.     return res[idx] = max(ans, longest_path[idx][0] + longest_path[idx][1]);
  67. }
  68.  
  69. int main()
  70. {
  71.     fread(buf,sizeof(char),1<<24,stdin);
  72.  
  73.     int n,a,b;
  74.     int ans= 0;
  75.     init();
  76.     n = getint();
  77.     pair<int,int> adj[N+1];
  78.     int edge[E];
  79.     rep(i,0,n-1)
  80.     {
  81.         a = getint();b = getint();
  82.         edge[i]=e;
  83.         addBiEdge(--a, --b);
  84.         adj[i]= make_pair(a,b);
  85.     }
  86.     rep(i,0,n-1)
  87.     {
  88.         a = adj[i].first; b = adj[i].second;
  89.         solve(a, b, edge[i]+1);
  90.         solve(b, a, edge[i]);
  91.     }
  92.     rep(i,0,n-1)
  93.         ans=max(ans, res[edge[i]]*res[edge[i]+1]);
  94.     printf("%d", ans);
  95.     return 0;
  96. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top