icontofig | 发布于 2020-03-04 13:04:20 | 阅读量 513 | 点分治 线段树
发布于 2020-03-04 13:04:20 | 点分治 线段树

题目大意

定义一种叫做前缀数组和的东西sum_i为某个数组的前缀和数组的前i项之和。

现在给定一个树,树上每个节点有权值,树上一条有向路径的权值定义为从起点u到终点v上的所有数字组成的前缀数组和。

求问这种路径权值的最大值是多少。

题解

此题解为搬运CodeForces官方题解,为其中文翻译版本。(严正声明,可能中间会加一些个人的理解,代码的话个人的代码感觉还不如官方的好看所以就放官方的题解代码了)

首先确认这是一个树上路径问题,针对树上路径问题,一般可用的方法就是树分治和树链剖分。

考虑到这道题的路径权值的定义,我们并不能用树链剖分的传统的LCA和线段树的方法来进行计算,我们大概需要用搜索算法才能确定一个路径的权值和长度。

但是问题是,路径总数实在太多了,我们是不可能把所有路径都找出来算一遍的。所以我们考虑采用点分治,看看如何去减少对路径的统计。

考虑使用树分治,这里使用点分治更为方便(当然我也不会边分治),因为下面的思路是依靠点分治经过树的重心的路径这一思路展开的。

我们考虑一个树,经过重心的一个路径u->rt->v,我们分成u->rt和rt前往v的路径的下面一个点x->v两条路径来看。

假设路径u->rt的路径权值为为presum、路径上所有点的值的和为precnt,路径x->v的路径的路径权值为precalc、长度为prelen。

那么u->v的路径的路径权值为:

sum = precnt*prelen + presum + precalc

这是一个一次函数的形式,可以看作是一个直线在某点处的取值问题。

具体而言可以看作一条斜率为prelen,参数为precalc的直线在x = precnt处的取值(最后再加上一个presum)

那么对于前半部分路径对后半部分路径进行组合结果计算的问题就转化成了求后半部分的路径代表的多个直线在某点处的取值的最大值问题(最高点)。

但是用什么来计算呢?暴力肯定行不通的。

这里介绍李超线段树。李超线段树的用途是,维护区间内最高的线段。其思想是线段树的每个节点保存在当前区间中心点mid处最高的线段。每当加入一条线段时,先检测当前区间中心点mid处这条线段的高度与原来的线段相比,然后更低的线段向其左/右孩子更新。李超线段树可以查询在某点处最高的高度为多少。具体实现可以看代码。

于是我们通过点分治和李超线段树可以成功地把此题的复杂度降低到O(nlog2n),并且成功计算出结果。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 150005;
typedef long long ll;
typedef pair<ll, ll> PI;
PI T[N<<2];
bool usedT[N<<2];
void clear(int v, int l, int r){
    if(!usedT[v]) return;
    usedT[v] = false;
    T[v] = make_pair(0ll, 0ll);
    if(l < r - 1){
        int m = (l + r) / 2;
        clear(v * 2 + 1, l, m);
        clear(v * 2 + 2, m, r);
    }
    return;
}
ll eval(PI f, int x){
    return f.first * x + f.second;
}
ll get(int v, int l, int r, int x){
    ll ans = eval(T[v], x);
    if(l < r - 1){
        int m = (l + r) / 2;
        if(m > x)
            ans = max(ans, get(v * 2 + 1, l, m, x));
        else
            ans = max(ans, get(v * 2 + 2, m, r, x));
    }
    return ans;
}
void upd(int v, int l, int r, PI f){
    usedT[v] = true;
    int m = (l + r) / 2;
    bool need_swap = eval(f, m) > eval(T[v], m);
    if(need_swap)
        swap(T[v], f);
    if(l == r - 1)
        return;
    if(eval(f, l) > eval(T[v], l))
        upd(v * 2 + 1, l, m, f);
    else
        upd(v * 2 + 2, m, r, f);
    return;
}
ll ans = 0;
void update_ans(vector<vector<PI> > heads, vector<vector<PI> > tails){
    int n = heads.size();
    for(int i = 0; i < n; i++){
        for(auto x : heads[i])
            ans = max(ans, get(0, 0, N, x.first) + x.second);
        for(auto x : tails[i])
            upd(0, 0, N, x);
    }
    clear(0, 0, N);
    return;
}
int a[N];
vector<int> g[N];
int n;
bool used[N];
int siz[N];
void dfs1(int x, int p = -1){
    if(used[x]) return;
    siz[x] = 1;
    for(auto to : g[x]){                    
        if(!used[to] && to != p){
            dfs1(to, x);
            siz[x] += siz[to];
        }
    }
    return;
}
pair<int, int> c;
int S = 0;
void find_centroid(int x, int p = -1){
    if(used[x]) return;
    int mx = 0;
    for(auto to : g[x]){
        if(!used[to] && to != p){
            find_centroid(to, x);
            mx = max(mx, siz[to]);
        }
    }
    if(p != -1)
        mx = max(mx, S - siz[x]);
    c = min(c, make_pair(mx, x));
    return;
}
void dfs_heads(int v, int p, int cnt, ll cursum, ll curadd, vector<PI>& sink){
    if(used[v])
        return;
    cnt++;
    curadd += a[v];
    cursum += curadd;
    sink.push_back(make_pair(cnt, cursum));
    for(auto to : g[v])
        if(to != p)
            dfs_heads(to, v, cnt, cursum, curadd, sink);
    return;
}
void dfs_tails(int v, int p, int cnt, ll cursum, ll curadd, vector<PI>& sink){
    if(used[v])
        return;
    cnt++;
    curadd += a[v];
    cursum += a[v] * 1ll * cnt;
    sink.push_back(make_pair(curadd, cursum));
    for(auto to : g[v])
        if(to != p)
            dfs_tails(to, v, cnt, cursum, curadd, sink);
    return;
}
void centroid(int v){
    if(used[v]) return;
    dfs1(v);
    S = siz[v];
    c = make_pair(int(1e9), -1);
    find_centroid(v);
    int C = c.second;
    used[C] = 1;
    vector<vector<PI> > heads, tails;
    for(auto to : g[C])
        if(!used[to]){
            heads.push_back(vector<PI>());
            dfs_heads(to, C, 1, a[C], a[C], heads.back());
            tails.push_back(vector<PI>());
            dfs_tails(to, C, 0, 0, 0, tails.back());
        }
    heads.push_back(vector<PI>({{1, a[C]}}));
    tails.push_back(vector<PI>({{0, 0}}));
    update_ans(heads, tails);
    reverse(heads.begin(), heads.end());
    reverse(tails.begin(), tails.end());
    update_ans(heads, tails);
    for(auto to : g[C])
        centroid(to);
    return;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);    
    }
    for(int i = 0; i < n; i++)
        cin >> a[i];
    centroid(0);
    cout << ans << endl;
    return 0;
}



内容更新于: 2020-03-04 13:04:20
链接地址: http://blog.leanote.com/post/icontofig/CodeForces-G.-Sum-of-Prefix-Sums

上一篇: SWERC 2019-2020 Problem A Environment-Friendly Travel DP+bfs

下一篇: CodeForces 1313.C2 Skyscrapers(hard version) nlogn线段树做法

513 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航