Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- _____ _ _ _ _
- |_ _| |__ ___ / \ _ __ ___| |__ _ _| |
- | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
- | | | | | | __// ___ \| | | \__ \ | | | |_| | |
- |_| |_| |_|\___/_/ \_\_| |_|___/_| |_|\__,_|_|
- */
- #include<bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define ll int
- #define pb push_back
- #define ppb pop_back
- #define endl '\n'
- #define mii map<ll,ll>
- #define msi map<string,ll>
- #define mis map<ll, string>
- #define rep(i,a,b) for(ll i=a;i<b;i++)
- #define repr(i,a,b) for(ll i=b-1;i>=a;i--)
- #define trav(a, x) for(auto& a : x)
- #define pii pair<ll,ll>
- #define vi vector<ll>
- #define vii vector<pair<ll, ll>>
- #define vs vector<string>
- #define all(a) (a).begin(),(a).end()
- #define F first
- #define S second
- #define sz(x) (ll)x.size()
- #define hell 1000000007
- #define lbnd lower_bound
- #define ubnd upper_bound
- #define max(a,b) (a>b?a:b)
- #define min(a,b) (a<b?a:b)
- /* For Debugging */
- #define DEBUG cerr<<"\n>>>I'm Here<<<\n"<<endl;
- #define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
- #define what_is(x) cerr << #x << " is " << x << endl;
- std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
- #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
- #define TIME cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
- #define DECIMAL(n) cout << fixed ; cout << setprecision(n);
- #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- using namespace __gnu_pbds;
- using namespace std;
- #define PI 3.141592653589793
- #define N 100005
- vi a[N];
- ll par[N],maxHeight[N],maxPath[N],ans[N];
- void fun(ll node,ll height,ll path) {
- vii tmp1,tmp2;
- tmp1.pb({height,-1});
- tmp2.pb({path,-1});
- for(auto i : a[node]) {
- if(i != par[node]) {
- tmp1.pb({maxHeight[i],i});
- tmp2.pb({maxPath[i],i});
- }
- }
- sort(all(tmp1));
- sort(all(tmp2));
- reverse(all(tmp1));
- reverse(all(tmp2));
- auto find_best_height = [&] (vi v) {
- set<ll> st;
- for(auto i:v) {
- st.insert(i);
- }
- trav(j,tmp1) {
- if(st.find(j.S)==st.end()) {
- return j.F;
- }
- }
- return 0;
- };
- auto find_best_two_height = [&] (ll i) {
- if(sz(tmp1)<=2) {
- return -2;
- }
- ll sum = 0,cnt = 2;
- trav(j,tmp1) {
- if(j.S!=i) {
- sum+=j.F;
- cnt--;
- if(cnt==0) {
- return sum;
- }
- }
- }
- return -2;
- };
- auto find_best_path = [&] (vi v) {
- set<ll> st;
- for(auto i:v) {
- st.insert(i);
- }
- trav(j,tmp2) {
- if(st.find(j.S)==st.end()) {
- return j.F;
- }
- }
- return 0;
- };
- for(auto i : a[node]) {
- if(i != par[node]) {
- fun(i,find_best_height({i}), max(find_best_two_height(i) + 2, find_best_path({i})));
- }
- }
- ans[node] = 0;
- for(auto i : tmp2) {
- ans[node] = max(ans[node],i.F * (find_best_two_height(i.S) + 2) );
- }
- // for(auto i:a[node]) {
- // if(i!=par[node]) {
- // ans[node] = max(ans[node],(height + maxHeight[i] + 2) * find_best_path({i,-1}));
- // }
- // }
- }
- void precalc(ll node) {
- vi tmp;
- for(auto i : a[node]) {
- if(par[node] != i) {
- par[i] = node;
- precalc(i);
- tmp.pb(-maxHeight[i]);
- maxHeight[node] = maxHeight[i] + 1;
- maxPath[node] = max(maxPath[node],maxPath[i]);
- }
- }
- if(sz(tmp) > 1) {
- sort(all(tmp));
- maxPath[node] = max(maxPath[node],-(tmp[0]+tmp[1]));
- }
- return;
- }
- void solve()
- {
- ll n,x,y;
- cin>>n;
- rep(i,1,n) {
- cin>>x>>y;
- a[x].pb(y);
- a[y].pb(x);
- }
- par[1] = -1;
- precalc(1);
- fun(1,0,0);
- ll pans=0;
- rep(i,1,n+1) {
- pans=max(pans,ans[i]);
- }
- cout<<pans<<endl;
- return;
- }
- int main()
- {
- FAST
- int TESTS=1;
- // cin>>TESTS;
- rep(i,0,TESTS)
- {
- // cout<<"Case #"<<i+1<<": ";
- solve();
- }
- TIME
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment