Codeforces 739B【树上倍增+差分】

59 阅读 0 评论 39 点赞

我是靠谱客的博主缓慢百褶裙，最近开发中收集的这篇文章主要介绍Codeforces 739B【树上倍增+差分】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思路：
差分其实是个自己随便创造的东西啊~
差分（这里的小差分）：
比如你要算一棵树上 u->v 路径上的次数， v是 u 子树上的一个点，
算一棵树上 u->v 路径上的次数在这了是算u -> v路径上除了 v 的每个节点的次数，
对于每一对u, v (u -> v)的，用C[i]计数，可以C[fa[ u ]]–, C[fa[ v ]]++ (fa[i] 是 i 的前驱节点), 然后跑一下DFS，统计次数，具体处理就是对于每个节点去加上他的所有子节点的次数，然后就会发现就这么搞好了。。
树上倍增：
福利：真讲的超级棒！！！
处理完倍增以后，就是每次找一个能“跳”的最远位置！
~~对于第一次应用倍增和差分，真是感觉非常...爽啊...~~

要多刷一波倍增的题了！！！

代码参考自：http://blog.csdn.net/cabinfever/article/details/53325717

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
#define mem(a,b) memset(a, b, sizeof(a))
#define LMid Left, Mid
#define RMid Mid+1,Right
#define Lson num<<1, Left, Mid
#define Rson num<<1|1, Mid + 1, Right

const int Maxn = 2e5 + 10;
struct Edge{int v,nex;LL w;}edge[Maxn<<1];
int n, head[Maxn], tol, f[Maxn][23];
LL w[Maxn], c[Maxn], dis[Maxn];
void init(){mem(head,-1);tol = 0;}
void add(int u,int v, LL w){
    edge[tol] = (Edge){v, head[u], w}, head[u] = tol++;
    edge[tol] = (Edge){u, head[v], w}, head[v] = tol++;
}

void DFS1(int u, int fa){
    int v, x = u;
    f[u][0] = fa;
    for(int i=1;i<20;i++) f[u][i] = f[f[u][i-1]][i-1];
    for(int i=19;i>=0;i--) while(x > 1 && dis[u] - dis[f[x][i]] <= w[u]) x = f[x][i];
    x = max(1, x);
    c[f[x][0]]--;
    c[f[u][0]]++;
    for(int i=head[u];~i;i=edge[i].nex){
        v = edge[i].v;
        if(v == fa) continue;
        dis[v] = dis[u] + edge[i].w;
        DFS1(v, u);
    }
}
void DFS2(int u, int fa){
    int v;
    for(int i=head[u];~i;i=edge[i].nex){
        v = edge[i].v;
        if(v == fa) continue;
        DFS2(v, u);
        c[u] += c[v];
    }
}

int main(){
    int p;
    LL q;
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%I64d", &w[i]);
    init();
    for(int i=2;i<=n;i++){
        scanf("%d%I64d",&p, &q);
        add(i, p, q);
    }
    DFS1(1, 0);
    DFS2(1, 0);
    for(int i=1;i<=n;i++)
        printf("%I64d ", c[i]);
    return 0;
}