点分治 线段树    发布于 2020-03-04   538人围观   0条评论

题目大意

定义一种叫做前缀数组和的东西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),并且成功计算出

查看更多
点分治 树状数组    发布于 2020-02-03   381人围观   0条评论

题解

树上点对距离问题,非常经典的点分治问题。

点分治的基本思路:

对于当前的树(子树),求出其重心,统计过重心的合法路径数,然后以重心为分隔点,分别递归对删除该重心后的子树进行求解(继续求重心、统计,再进行递归)。

重心的概念:若一个点为树的重心,那么其作为根的时候,其子树的大小的最大值最小。

重心的性质:重心分割出的子树的大小不会超过now_n/2,可以用来证明其时间复杂度为O(logn * 统计的时间)。

此题要求距离小于等于k的路径数目,如果把每一种都算出来累加复杂度是相当高的。

可以使用树状数组,不过要注意树状数组的0号位对答案是不会造成任何影响的,所以在统计入树状数组的时候要稍微处理一下。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
struct edge{
    int to,next,val;
}e[maxn<<1];
int siz[maxn],mx[maxn],vis[maxn],dis[maxn];
int c[maxn*100],tmp[maxn];
int n,rt;
int h[maxn];
int lowbit(int x){
    return x & -x;
}
void update(int now,int d){
    while(now <= n * 100 - 2){
        c[now] += d;
        now += lowbit(now);
    }
    return;
}
int query(int now){
    int ret = 0;
    while(now > 0){
        ret += c[now];
        now -= lowbit(now);
    }
    return ret;
}
int cnt = 0,num = 0,sum = 0;
void add(int u,int v,int d){
    e[cnt].to = v;e[cnt].val = d;e[cnt].next = h[u];h[u] = cnt++;
    return;
}
void get_root(int now,int fa){
    siz[now] = 1;mx[n
查看更多