IZhO 2017. Problem F. Hard route

Original link: https://www.shuizilong.com/house/archives/izho-2017-problem-f-hard-route/

• https://oj.uz/problem/view/IZhO17_road

It is very easy to write if the number of solutions is not considered. Similar to the previous question, we only need to maintain the downward top3 and upward top1.

Then use the mean inequality to get the optimal solution must be a*(b+c) | a >= b >= c.

  
   
#include <lastweapon/io>  
   
using namespace lastweapon;  
   
  
   
const int N = int(1e5) + 9;  
   
  
   
int dn[N][3], up[N];  
   
VI adj[N]; int n;  
   
  
   
void upd(int d[], int v) {  
   
    if (v > d[0]) d[2] = d[1], d[1] = d[0], d[0] = v;  
   
    else if (v > d[1]) d[2] = d[1], d[1] = v;  
   
    else if (v > d[2]) d[2] = v;  
   
}  
   
  
   
void dfs1(int u = 1, int p = 0) {  
   
    for (auto v: adj[u]) if (v != p) {  
   
        dfs1(v, u);  
   
        upd(dn[u], dn[v][0] + 1);  
   
    }  
   
}  
   
  
   
void dfs2(int u = 1, int p = 0) {  
   
    for (auto v: adj[u]) if (v != p) {  
   
        checkMax(up[v], max(up[u], dn[u][0] != dn[v][0] + 1 ? dn[u][0] : dn[u][1]) + 1);  
   
        dfs2(v, u);  
   
    }  
   
}  
   
  
   
LL f(int x) {  
   
    if (dn[x][1] == 0) return 0;  
   
    if (up[x] > dn[x][0]) return (LL)up[x] * (dn[x][0] + dn[x][1]);  
   
    if (up[x] > dn[x][2]) return (LL)dn[x][0] * (up[x] + dn[x][1]);  
   
    if (dn[x][2] == 0) return 0;  
   
    return (LL)dn[x][0] * (dn[x][1] + dn[x][2]);  
   
}  
   
  
   
int main() {  
   
  
   
#ifndef ONLINE_JUDGE  
   
    freopen("in.txt", "r", stdin);  
   
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);  
   
#endif  
   
  
   
    DO(RD(n)-1) {  
   
        int x, y; RD(x, y);  
   
        adj[x].PB(y);  
   
        adj[y].PB(x);  
   
    }  
   
  
   
    dfs1(); dfs2();  
   
  
   
    LL z = 0; REP_1(i, n) checkMax(z, f(i));  
   
    cout << z << endl;  
   
}  
   
  
   

This article is transferred from: https://www.shuizilong.com/house/archives/izho-2017-problem-f-hard-route/
This site is only for collection, and the copyright belongs to the original author.