欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【jzoj5338】【NOIP2017提高A组模拟8.25】【影子】【点分治】

程序员文章站 2024-02-11 23:37:28
...

description

【jzoj5338】【NOIP2017提高A组模拟8.25】【影子】【点分治】

有必要说明一下,下面的点分治在菊花图上会tle。

solution

直接点分治,维护点权最小值和边权和,按点权最小值排序,两个指针维护一下最大值即可。

code

#include<set>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int const mn=1e5+9,mm=2*1e5+9,mo=1<<30;
int t,n,gra,begin[mn],to[mm],len[mm],next[mm],size[mn],vis[mn],cntb,w[mn];
LL ans;
void insert(int u,int v,int w){
    to[++gra]=v;
    len[gra]=w;
    next[gra]=begin[u];
    begin[u]=gra;
}
void gsize(int p,int q){
    size[p]=1;
    fr(i,p)if((to[i]!=q)&&(!vis[to[i]])){
        gsize(to[i],p);
        size[p]+=size[to[i]];
    }
}
int groot(int p,int q,int lim){
    fr(i,p)if((to[i]!=q)&&(!vis[to[i]])){
        int tmp=groot(to[i],p,lim);
        if(tmp)return tmp;
    }
    if(size[p]>lim)return p;
    return 0;
}
struct rec{
    int mi;
    LL sum;
    friend bool operator<(rec x,rec y){
        return x.mi<y.mi;
    }
};
rec a[mn],b[mn],c[mn];
void dfs(int p,int q,int mi,LL sum){
    b[++cntb].mi=mi;
    b[cntb].sum=sum;
    fr(i,p)if((to[i]!=q)&&(!vis[to[i]]))
        dfs(to[i],p,min(mi,w[to[i]]),sum+len[i]);
}
LL calc(rec *a,int cnta,rec *b,int cntb){
    LL tmp=0,mx=0;
    for(int i=cnta,j=cntb+1;i;i--){
        while((j>1)&&(b[j-1].mi>=a[i].mi))j--,mx=max(mx,b[j].sum);
        tmp=max(tmp,a[i].mi*(a[i].sum+mx));
    }
    return tmp;
}
void solve(int p){
    gsize(p,0);
    p=groot(p,0,size[p]/2);
    vis[p]=1;
    int cnta=0;
    fr(i,p)if(!vis[to[i]]){
        cntb=0;
        dfs(to[i],p,min(w[p],w[to[i]]),len[i]);
        sort(b+1,b+cntb+1);
        ans=max(ans,calc(a,cnta,b,cntb));
        ans=max(ans,calc(b,cntb,a,cnta));
        int cntc=0;
        for(int j=1,k=1;(j<=cnta)||(k<=cntb);){
            cntc++;
            if((k>cntb)||((j<=cnta)&&(a[j].mi<b[k].mi))){
                c[cntc].mi=a[j].mi;
                c[cntc].sum=a[j].sum;
                j++;
            }else{
                c[cntc].mi=b[k].mi;
                c[cntc].sum=b[k].sum;
                k++;
            }
        }
        cnta=cntc;
        fo(j,1,cntc){
            a[j].mi=c[j].mi;
            a[j].sum=c[j].sum;
        }
    }
    fr(i,p)if(!vis[to[i]])solve(to[i]);
}
int main(){
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    scanf("%d",&t);
    fo(cas,1,t){
        scanf("%d",&n);
        fo(i,1,n)scanf("%d",&w[i]),vis[i]=0;
        gra=0;
        fo(i,1,n)begin[i]=0;
        fo(i,1,n-1){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            insert(u,v,w);
            insert(v,u,w);
        }
        ans=0;
        solve(1);
        printf("%lld\n",ans);
    }
    return 0;
}