好难啊

Problem

给定一棵 N 个点的树，求树上一条链使得链的长度乘链上所有点中的最小权值所得的积最大。
其中链长度定义为链上点的个数。

$n\leq 50000$

Solution

假设我们点从大到小插入

那么树的直径一定越来越大

所以问题就在于怎么维护任意两个子树合并之后的直径了

定理：新加入的点后一棵树的直径的端点一定是原来树的直径端点和这个点的三选一。

我们如果再给这个点加入一条路径，原理肯定也一样。

所以我们只需处理一棵子树以一个点为根的最深深度，与另一个子树的一个点合并就行。

这样的话复杂度就被优化到了一个子树的大小级别。

这样的复杂度是可以使用启发式合并优化到 $O(n\log n)$ 的。

Code

// Code by ajcxsu
// Problem: path on tree

#include<bits/stdc++.h>
using namespace std;

const int N=5e4+10, M=1e5+10;
int h[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
int w[N];


int dfn[N], siz[N], fa[N], dep[N], son[N], top[N], idx;
void dfs1(int x=1, int k=1) {
    dep[x]=k, siz[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(!dep[to[u]]) {
            fa[to[u]]=x, dfs1(to[u], k+1), siz[x]+=siz[to[u]];
            if(siz[to[u]]>siz[son[x]]) son[x]=to[u];
        }
}
void dfs2(int x=1, int t=1) {
    top[x]=t, dfn[x]=++idx;
    if(son[x]) dfs2(son[x], t);
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) dfs2(to[u], to[u]);
}
int dis(int s, int t) {
    int ns=s, nt=t, l;
    while(top[s]!=top[t]) {
        if(dep[top[s]]<dep[top[t]]) swap(s, t);
        s=fa[top[s]];
    }
    l=dep[s]<dep[t]?s:t;
    return dep[ns]+dep[nt]-(dep[l]<<1);
}
int Fa[N], du[N], dv[N], Siz[N];
int Find(int x) { return Fa[x]?Fa[x]=Find(Fa[x]):x; }
vector<int> val[65540];

int lim, k, na;
void dfs3(int x, int nk, int fr) {
    if(nk>k) k=nk, na=x;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fr && Find(to[u])==lim) dfs3(to[u], nk+1, x);
}
int Union(int a, int b) {
    int af=Find(a), bf=Find(b);
    if(Siz[af]<Siz[bf]) swap(af, bf), swap(a, b);
    if(af==bf) return -1;
    int ru=du[af], rv=dv[af];
    na=a, k=0, lim=bf, dfs3(b, 1, 0);
    int va, vb, vc, vd;
    va=dis(ru, rv), vb=dis(ru, a)+k, vc=dis(rv, a)+k, vd=max(va, max(vb, vc));
    if(vd==va) du[bf]=ru, dv[bf]=rv;
    else if(vd==vb) du[bf]=ru, dv[bf]=na;
    else if(vd==vc) du[bf]=rv, dv[bf]=na;
    return Fa[af]=bf, Siz[bf]+=Siz[af], vd;
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i], val[w[i]].push_back(i), du[i]=dv[i]=i, Siz[i]=1;
    int u, v;
    for(int i=1;i<n;i++) cin>>u>>v, ins(u, v), ins(v, u);
    dfs1(), dfs2();
    long long ans=0;
    int ndis;
    for(int i=65536;i>=0;i--)
        for(int j=0, k=val[i].size(); j<k; j++) {
            v=val[i][j];
            for(int u=h[v];u;u=nexp[u])
                if(w[to[u]]>=i) {
                    ndis=Union(v, to[u]);
                    ans=max(1ll*(ndis+1)*i, ans);
                }
        }
    cout<<ans<<endl;
    return 0;
}