2870: 最长道路tree

链接

https://www.lydsy.com/JudgeOnline/problem.php?id=2870

思路

先把树转化为二叉树

再链分治

%%yyb

代码

#include <iostream>

#include <algorithm>

#include <cstring>

#include <utility>

#include <cstdio>

#include <vector>

#define ll long long

using namespace std;

const int N=4e5+7,inf=0x3f3f3f3f;

int read() {

    int x=0,f=1;char s=getchar();

    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

    return x*f;

}

int n,sdgzy,w[N];

ll ans;

struct node {

    int v,nxt,w;

}e[N];

int head[N],mvp;

void Add(int u,int v,int q) {

    e[++mvp].v=v;

    e[mvp].w=q;

    e[mvp].nxt=head[u];

    head[u]=mvp;

}

vector<int> G[N];

void dfs(int u,int f) {

    for(int i=head[u];i;i=e[i].nxt) {

        int v=e[i].v;

        if(v==f) continue;

        G[u].push_back(v);

        dfs(v,u);

    }

}

void rebuild() {

    mvp=1,memset(head,0,sizeof(head));

    for(int i=1;i<=n;++i) {

        int tmp=G[i].size();

        if(tmp<=2) {

            for(int j=0;j<tmp;++j) Add(i,G[i][j],G[i][j]<=sdgzy),Add(G[i][j],i,G[i][j]<=sdgzy);

        } else {

            int a=++n,b=++n;w[a]=w[b]=w[i];

            Add(a,i,0),Add(i,a,0),Add(b,i,0),Add(i,b,0);

            for(int j=0;j<tmp;++j) {

                if(j&1) G[a].push_back(G[i][j]);

                else G[b].push_back(G[i][j]);

            }

        }

    }

}

bool vis[N];

int rt,rt_val,siz[N];

void get_rt(int u,int f,int tot) {

    siz[u]=1;

    for(int i=head[u];i;i=e[i].nxt) {

        int v=e[i].v;

        if(vis[i>>1]||v==f) continue;

        get_rt(v,u,tot);

        siz[u]+=siz[v];

        int tmp=max(siz[v],tot-siz[v]);

        if(tmp<rt_val) rt_val=tmp,rt=i;

    }

}

int top[2];

pair<int,int> SX[2][N];

void get_dis(int u,int f,int mi,int dep,int opt) {

    mi=min(mi,w[u]);

    SX[opt][++top[opt]]=make_pair(mi,dep);

    for(int i=head[u];i;i=e[i].nxt) {

        int v=e[i].v;

        if(vis[i>>1]||v==f) continue;

        get_dis(v,u,mi,dep+e[i].w,opt);

    }

}

bool cmp(pair<int,int> a,pair<int,int> b) {return a>b;}

void solve(int u,int tot) {

    rt_val=inf;

    get_rt(u,0,tot);

    if(rt_val >= inf) return;

    vis[rt>>1]=1;

    ll ls=e[rt].v,rs=e[rt^1].v;//bian fen zhi

    top[0]=top[1]=0;

    get_dis(ls,u,inf,0,0);

    get_dis(rs,u,inf,0,1);

    sort(SX[0]+1,SX[0]+1+top[0],cmp);

    sort(SX[1]+1,SX[1]+1+top[1],cmp);

    int ma=0;

    for(int i=1,j=1;i<=top[0];++i) {

        while(j<=top[1]&&SX[1][j].first>=SX[0][i].first) ma=max(ma,SX[1][j].second),j++;

        if(j-1<=top[1]&&SX[1][j-1].first>=SX[0][i].first)

        ans=max(ans,1LL*SX[0][i].first*(SX[0][i].second+ma+1+e[rt].w));//dian = bian + 1

        // if(j>top[1]) break;

    }

    ma=0;

    for(int i=1,j=1;i<=top[1];++i) {

        while(j<=top[0]&&SX[0][j].first>=SX[1][i].first) ma=max(ma,SX[0][j].second),j++;

        if(j-1<=top[0]&&SX[0][j-1].first>=SX[1][i].first)

            ans=max(ans,1LL*SX[1][i].first*(SX[1][i].second+ma+1+e[rt].w));

        // if(j>top[0]) break;

    }

    int a=siz[ls],b=tot-a;

    solve(ls,a);

    solve(rs,b);

}

int main() {

    // freopen("a.in","r",stdin);

    // freopen("a.out","w",stdout);

    n=read();sdgzy=n;

    for(int i=1;i<=n;++i) w[i]=read();

    for(int i=1;i<n;++i) {

        int x=read(),y=read();

        Add(x,y,0),Add(y,x,0);

    }

    dfs(1,0);

    rebuild();

    solve(1,n);

    cout<<ans<< "\n";

    return 0;

}