codeforces 739b Alyona and a tree

1
2
给定一棵树，每个节点有一个值a(u)，每条边有一个权值w，定义节点u控制节点v当且仅当dis(u,v) <= a(v)。要求每个节点控制的点数。

1
2
首先求出每个节点到根节点的前缀边权和pre[u],那么dis(u,v) = dis[v] - dis[u] -> dis[v] - dis[u] <= a[v] ->  dis[v] - a[v] <= dis[u].问题转化为了求树上节点的子节点的a值比该节点的b值小的点数。可以用dfs序转化为求区间中小于定值的数个数。离线树状数组即可。

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define lowbit(x) x&(-x)
using namespace std;
typedef struct node node;
typedef struct query query;
struct query
{
    int l,r;
    long long a,b;
    int id;
    /* data */
}q[201000];
struct node
{
    int to,next,w;
}edge[201000];
int cnt,head[201000];
long long wu[201000],pre[201000];
query num[201000];
long long tree[601000];
long long ans[201000];
int n,m,maxn,dfs_clock,qnum;
void update(int x,int b){
    for(;x <= n;x += lowbit(x)){
        tree[x] += b;
    }
}

int cmp(query a,query b){
    return a.a < b.a;
}

int cmp1(query a,query b){
    return a.b < b.b;
}

long long get(int x){
    long long res = 0;
    for(;x;x -= lowbit(x)){
        res += tree[x];
    }
    return res;
}

void add(int u,int v,int w){
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    edge[cnt].w = w;
    head[u] = cnt++;
}

void dfs(int u,int fa,int w){
    pre[u] = pre[fa] + w;
    int tmp = qnum++;
    q[tmp].l = ++dfs_clock;
    q[tmp].b = pre[u];
    q[tmp].a = pre[u] - wu[u];
    q[tmp].id = u;
    for(int i =head[u];i != -1;i = edge[i].next){
        dfs(edge[i].to,u,edge[i].w);
    }
    q[tmp].r = dfs_clock;
}

void solve(){
    for(int i = 0;i < n;i ++){
        num[i] = q[i];
    }
    sort(num,num + n,cmp);
    sort(q,q+n,cmp1);
    int now = 0;
    for(int i = 0;i < n;i ++){
        //printf("i%d %d %dn",i,q[i].l,q[i].r );
        while(now < n && num[now].a <=q[i].b){
            update(num[now].l,1);
            now++;
        }
        ans[q[i].id] = get(q[i].r) - get(q[i].l - 1);
        ans[q[i].id] --;
    }
    for(int i = 1;i <= n;i ++) printf("%lld%c",ans[i],i == n?'n':' ');
}

void debug(){

}

int main(){
    scanf("%d",&n);
    for(int i =1;i <= n;i ++) scanf("%lld",&wu[i]);
    memset(head,-1,sizeof(head));
    memset(tree,0,sizeof(tree));
    qnum = 0;
    cnt = 0;
    dfs_clock = 0;
    int f,w;
    for(int i = 2;i <= n;i ++){
        scanf("%d%d",&f,&w);
        add(f,i,w);
    }
    pre[0] = 0;
    dfs(1,0,0);
    solve();
    return 0; 
}