树上差分（附习题洛谷P3258&P2680）

Swing_YL · 2018-10-16 21:05:25 · 个人记录

树上差分

树上差分分为两种：

①点差分：

差分数组中，路径起点+1,路径终点+1，lca-1，fa[lca]-1。原因是：

在每条深搜的路径中，回溯时父亲会加上子节点。

红色为路径。

这样，在遍历时，回溯时，（一步步来），先变成这样（遍历左子树）：

再变成（遍历右子树）：

于是差分数组就处理好了，代表的是每个点经过几次。

P3258

题意为按顺序遍历一些点，每遍历到一个点，答案就+1，最后一个点答案不用加。

裸的树上点差分。

唯一一个细节就是，把2-n答案全减一，因为一个点作为终点，加了一，有作为下一条路的起点加了一，所以减回来。

②边差分：

差分数组中，路径起点+1,路径终点+1，lca-2。原因是：

（用点代表它上边的边）

P2680

因为所有计划同时进行，所以让计划里的最大值最小即可，可以想到二分。

二分一个完成时间，将所有不能在deadline以内的放在树上差分，得到每个边的经过的次数，如果它们有一条公共边（所有>mid的路径都经过它），并且让这条边免费，时间<mid,则成立。

bool check(LL mid){
    sum=F=0;
    memset(cnt,0,sizeof cnt);//查分数组
    for(LL i=1;i<=k;i++)
        if(z[i]>mid){
            F=max(F,z[i]);//因为要让所有时间减去公共边小于mid，所以直接让最大边减去
            cnt[u[i]]++;
            cnt[v[i]]++;
            cnt[w[i]]-=2;
            sum++;//几个>mid的
        }
    if(!sum) return 1;
    work(1);//即统计差分
    for(LL i=1;i<=n;i++)
        if(cnt[i]==sum&&F-d[i]<=mid) //这条边是公共边并且让这条边免费，所有路径满足条件
        return 1;
    return 0;
}