Codeforces Round #381 (Div. 2) D. Alyona and a tree 树上二分+前缀和思想

时间：2022-09-10 20:33:23

题目链接：

http://codeforces.com/contest/740/problem/D

D. Alyona and a tree

time limit per test2 secondsmemory limit per test256 megabytes
#### 问题描述
> Alyona has a tree with n vertices. The root of the tree is the vertex 1. In each vertex Alyona wrote an positive integer, in the vertex i she wrote ai. Moreover, the girl wrote a positive integer to every edge of the tree (possibly, different integers on different edges).
>
> Let's define dist(v, u) as the sum of the integers written on the edges of the simple path from v to u.
>
> The vertex v controls the vertex u (v ≠ u) if and only if u is in the subtree of v and dist(v, u) ≤ au.
>
> Alyona wants to settle in some vertex. In order to do this, she wants to know for each vertex v what is the number of vertices u such that v controls u.
#### 输入
> The first line contains single integer n (1 ≤ n ≤ 2·105).
>
> The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the integers written in the vertices.
>
> The next (n - 1) lines contain two integers each. The i-th of these lines contains integers pi and wi (1 ≤ pi ≤ n, 1 ≤ wi ≤ 109) — the parent of the (i + 1)-th vertex in the tree and the number written on the edge between pi and (i + 1).
>
> It is guaranteed that the given graph is a tree.
#### 输出
> Print n integers — the i-th of these numbers should be equal to the number of vertices that the i-th vertex controls
####样例输入
> 5
> 2 5 1 4 6
> 1 7
> 1 1
> 3 5
> 3 6
####样例输出
> 1 0 1 0 0

题意

给你一颗点权为a[i],的带边权的有根树(树根为1),对于节点v和它的子节点u之间，我们称v控制了u当且仅当dis(v,u)<=a[u]的时候，现在让你求每个结点能控制的子节点的个数。

题解

二分+前缀和。

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define scf scanf

#define prf printf

typedef __int64 LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=2e5+10;

int n;

int arr[maxn];

VPII G[maxn];

LL dep[maxn];

///ans维护的是前缀和，这里的前缀指的是从叶子到根的方向

int ans[maxn];

///path维护当前的一条路径

vector<pair<LL,int> > path;

void dfs(int u){

    ///自己肯定能够的到自己

    ans[u]++;

    ///二分找第一个dis(ancestor,u)>arr[u]既dep[u]-dep[ancestor]>arr[u]既dep[u]-arr[u]>dep[ancesotor];

    int p=lower_bound(all(path),mkp(dep[u]-arr[u],-1))-path.begin()-1;

    if(p>=0) ans[path[p].Y]--;

    path.pb(mkp(dep[u],u));

    for(int i=0;i<G[u].sz();i++){

        int v=G[u][i].X;

        dep[v]=dep[u]+G[u][i].Y;

        dfs(v);

        ans[u]+=ans[v];

    }

    path.pop_back();

}

int main(){

    clr(ans,0);

    scf("%d",&n);

    for(int i=1;i<=n;i++) scf("%d",&arr[i]);

    for(int v=2;v<=n;v++){

        int u,w;

        scf("%d%d",&u,&w);

        G[u].pb(mkp(v,w));

    }

    dep[1]=0;

    dfs(1);

    for(int i=1;i<=n;i++){

        prf("%d",ans[i]-1);

        if(i==n) prf("\n");

        else prf(" ");

    }

    return 0;

}

//end----------------------------------------------------------------------

树上倍增+前缀和

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define scf scanf

#define prf printf

typedef __int64 LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=2e5+10;

const int maxm=22;

int n;

int arr[maxn];

VPII G[maxn];

///anc[i][j]表示i节点的2^j的祖先

int anc[maxn][maxm];

int ans[maxn];

LL dep[maxn];

void dfs(int u,int f){

    ans[u]++;

    anc[u][0]=f;

    for(int i=1;i<maxm;i++){

        anc[u][i]=anc[anc[u][i-1]][i-1];

    }

    ///树上倍增

    int pos=u;

    for(int i=maxm-1;i>=0;i--){

        int tmp=anc[pos][i];

        if(dep[u]-dep[tmp]<=arr[u]){

            pos=tmp;

        }

    }

    pos=anc[pos][0];

    ans[pos]--;

    for(int i=0;i<G[u].sz();i++){

        int v=G[u][i].X;

        dep[v]=dep[u]+G[u][i].Y;

        dfs(v,u);

        ans[u]+=ans[v];

    }

}

int main(){

    clr(ans,0);

    scf("%d",&n);

    for(int i=1;i<=n;i++) scf("%d",&arr[i]);

    for(int v=2;v<=n;v++){

        int u,w;

        scf("%d%d",&u,&w);

        G[u].pb(mkp(v,w));

    }

    dep[1]=0;

    dfs(1,0);

    for(int i=1;i<=n;i++){

        prf("%d",ans[i]-1);

        if(i==n) prf("\n");

        else prf(" ");

    }

    return 0;

}

//end-----------------------------------------------------------------------

相关文章