【Codeforces 1303G】Sum of Prefix Sums | Mrsrz's blog

点分治，李超树。

题目大意：

给定一棵树，点带点权。要求找到一条有向路径，对路径上的点权依次排列，并进行前缀和，然后求和。要使得最后的和最大。求这个最大的和。

题解：

考虑点分治。

对于点 $x$ 作为分治中心，一条路径的信息记为 $(c,s)$，表示共经过 $c$ 个点，其前缀和的和为 $s$。那么，对于路径 $u\rightarrow x$ 和 $(x)\rightarrow v$（$(x)$ 表示不包含 $x$ 这个点），其信息为 $(c_1,s_1)$ 和 $(c_2,s_2)$，其合并后的路径的前缀和的和，可以表示为 $s_1\cdot (c_2+1)+s_2$。

我们发现，对于一组 $(c_2,s_2)$，它的值由 $s_1$ 决定，并且是个一次函数。

我们希望对于每个 $s_1$ 求出最大值。这个最大值显然会出现在这些一次函数围成的凸包上。

使用动态开点李超树来维护凸包即可。

涉及的操作是全局修改，区间查询，所以单层的时间复杂度为 $O(n\log n)$。

总时间复杂度 $O(n\log^2 n)$。

比赛的时候点分治写挂了……

Code：

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
const int N=150005;
typedef long long LL;
LL ans;
const LL INF=1e14;
int n,head[N],cnt,mx[N],sz[N],allsz,rt,w[N];
bool vis[N];
struct edge{
    int to,nxt;
}e[N<<1];
int root;
namespace SGT{
    struct _1{
        LL k,b;
        inline LL operator()(LL x)const{return k*x+b;}
    }A[N*120];
    int ls[N*120],rs[N*120],nod;
    void insert(int&o,LL l,LL r,const LL&k,const LL&b){
        if(!o){
            o=++nod;
            ls[o]=rs[o]=0;
            A[o]=(_1){k,b};
            return;
        }
        const LL yL=A[o](l),yR=A[o](r),nL=k*l+b,nR=k*r+b;
        if(yL>=nL&&yR>=nR)return;
        if(yL<=nL&&yR<=nR){
            A[o]=(_1){k,b};
            return;
        }
        if(l==r)return;
        const LL mid=l+r>>1;
        insert(ls[o],l,mid,k,b);
        insert(rs[o],mid+1,r,k,b);
    }
    LL query(int o,LL l,LL r,const LL&x){
        if(!o)return 0;
        if(l==r)return A[o](x);
        const LL mid=l+r>>1;
        if(x<=mid)
        return max(A[o](x),query(ls[o],l,mid,x));
        return max(A[o](x),query(rs[o],mid+1,r,x));
    }
}
void getroot(int now,int pre){
    sz[now]=1,mx[now]=0;
    for(int i=head[now];i;i=e[i].nxt)
    if(e[i].to!=pre&&!vis[e[i].to]){
        getroot(e[i].to,now);
        sz[now]+=sz[e[i].to];
        mx[now]=max(mx[now],sz[e[i].to]);
    }
    mx[now]=max(mx[now],allsz-sz[now]);
    if(!rt||mx[now]<mx[rt])rt=now;
}
pair<LL,int>down[N];
int top;
LL up[N],ddn[N];
void dfs(int now,int pre,int dep,LL u,LL d,LL sm){
    up[++top]=u,down[top]=make_pair(d,dep);ddn[top]=sm;
    for(int i=head[now];i;i=e[i].nxt)if(e[i].to!=pre&&!vis[e[i].to]){
        dfs(e[i].to,now,dep+1,u+(dep+1)*(LL)w[e[i].to],d+sm+w[e[i].to],sm+w[e[i].to]);
    }
}
void doit(int now){
    SGT::nod=root=0;
    vector<int>vc;
    for(int i=head[now];i;i=e[i].nxt)if(!vis[e[i].to]){
        vc.push_back(e[i].to);
        top=0;
        dfs(e[i].to,0,1,w[e[i].to],w[e[i].to],w[e[i].to]);
        for(int j=1;j<=top;++j){
            LL zb=up[j]+ddn[j]+w[now];
            LL s=ddn[j]+w[now];
            LL mxx=SGT::query(root,0,INF,s);
            ans=max(ans,mxx+zb);
        }
        for(int j=1;j<=top;++j){
            SGT::insert(root,0,INF,down[j].second,down[j].first);
        }
    }
    SGT::nod=root=0;
    for(int i=(int)vc.size()-1;~i;--i){
        int to=vc[i];
        top=0;
        dfs(to,0,1,w[to],w[to],w[to]);
        for(int j=1;j<=top;++j){
            LL zb=up[j]+ddn[j]+w[now];
            LL s=ddn[j]+w[now];
            LL mxx=SGT::query(root,0,INF,s);
            ans=max(ans,mxx+zb);
        }
        for(int j=1;j<=top;++j){
            SGT::insert(root,0,INF,down[j].second,down[j].first);
        }
    }
}
void solve(int now){
    vis[now]=1;
    doit(now);
    int sm=allsz;
    for(int i=head[now];i;i=e[i].nxt)
    if(!vis[e[i].to]){
        allsz=sz[e[i].to]>sz[now]?sm-sz[now]:sz[e[i].to];
        rt=0;
        getroot(e[i].to,now);
        solve(rt);
    }
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
    }
    for(int i=1;i<=n;++i)cin>>w[i];
    allsz=n,rt=0;
    getroot(1,0);
    solve(rt);
    cout<<ans<<'\n';
    return 0;
}