739B Codeforces Alyona and a tree 树上差分+二分（倍增）

137 阅读 0 评论 91 点赞

我是靠谱客的博主高高镜子，这篇文章主要介绍739B Codeforces Alyona and a tree 树上差分+二分（倍增），现在分享给大家，希望可以做个参考。

题目大意是给出一棵有根树，树上每个点、每条边都有一个权值。

现在给出“控制”的定义：对一个点u，设点v在其子树上，且 $dis(u,v) le a_v$ ，则称u控制v。

要求求出每个点控制了多少个点

模拟dfs过程，我们很容易发现dfs到点u时，其祖先节点到根的dis值都已经算出，且是单调递增，所以我们可以用二分或者倍增，在log的时间复杂度内找到深度最小的满足 $dis(u,v) le a_u$ 的点了。找到点v后，v到fa（u）上的每个点的答案都要增加1，显然用树上差分来实现，对ans[fa[v]]–,ans[fa[u]]++

复制代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <iostream>

using namespace std;

const int maxn = 200010;
const int lg = 20;

int n;
long long a[maxn];
long long c[maxn];
struct edge
{
    int v,w,next;
}e[maxn << 1];
long long dep[maxn];
int h[maxn],num = 0;
int f[maxn][lg+1];
int u,v;
long long w;

void build(int u,int v,int w)
{
    num++;
    e[num].v = v;
    e[num].w = w;
    e[num].next = h[u];
    h[u] = num;
}

void dfs1(int x,int fa)
{
    int v;
    f[x][0] = fa;
    for(int i = 1; i < lg; i++)
        f[x][i] = f[f[x][i-1]][i-1];
    int u = x;
    for(int i = lg - 1; i >= 0; i--)
        while(u > 1 && dep[x] - dep[f[u][i]] <= a[x])
            u = f[u][i];
    u = max(1,u);
    c[f[u][0]]--;
    c[f[x][0]]++;
    for(int i = h[x]; i; i = e[i].next)
    {
        v = e[i].v;
        if(v != fa)
        {
            dep[v] = dep[x] + e[i].w;
            dfs1(v,x);
        }
    }
}

void dfs2(int x,int f)
{
    int v;
    for(int i = h[x]; i; i = e[i].next)
    {
        v = e[i].v;
        if(v != f)
        {
            dfs2(v,x);
            c[x] += c[v];
        }
    }
}

int main()
{
    freopen("1.in","r",stdin);
    cin >> n;
    for(int i = 1; i <= n; i++)
        scanf("%I64d",&a[i]);
    for(int i = 2; i <= n; i++)
    {
        scanf("%d%I64d",&v,&w);
        build(i,v,w);
        build(v,i,w);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i = 1; i <= n; i++)
        printf("%I64d%c",c[i],i == n ? 'n' : ' ');
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <iostream>

using namespace std;

const int maxn = 200010;
const int lg = 20;

int n;
long long a[maxn];
long long c[maxn];
struct edge
{
    int v,w,next;
}e[maxn << 1];
long long dep[maxn];
int h[maxn],num = 0;
int f[maxn][lg+1];
int u,v;
long long w;

void build(int u,int v,int w)
{
    num++;
    e[num].v = v;
    e[num].w = w;
    e[num].next = h[u];
    h[u] = num;
}

void dfs1(int x,int fa)
{
    int v;
    f[x][0] = fa;
    for(int i = 1; i < lg; i++)
        f[x][i] = f[f[x][i-1]][i-1];
    int u = x;
    for(int i = lg - 1; i >= 0; i--)
        while(u > 1 && dep[x] - dep[f[u][i]] <= a[x])
            u = f[u][i];
    u = max(1,u);
    c[f[u][0]]--;
    c[f[x][0]]++;
    for(int i = h[x]; i; i = e[i].next)
    {
        v = e[i].v;
        if(v != fa)
        {
            dep[v] = dep[x] + e[i].w;
            dfs1(v,x);
        }
    }
}

void dfs2(int x,int f)
{
    int v;
    for(int i = h[x]; i; i = e[i].next)
    {
        v = e[i].v;
        if(v != f)
        {
            dfs2(v,x);
            c[x] += c[v];
        }
    }
}

int main()
{
    freopen("1.in","r",stdin);
    cin >> n;
    for(int i = 1; i <= n; i++)
        scanf("%I64d",&a[i]);
    for(int i = 2; i <= n; i++)
    {
        scanf("%d%I64d",&v,&w);
        build(i,v,w);
        build(v,i,w);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i = 1; i <= n; i++)
        printf("%I64d%c",c[i],i == n ? 'n' : ' ');
    return 0;
}