CodeForces 740D Alyona and a tree 题解：DFS + 二分

文章目录

Problem
Input
Output
Examples
- Input #1
- Output #1
- Input #2
- Output #2
Notes
Solution
Code

题目链接
vector 真的好用～

Problem

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 $a_i$ . 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) ≤ a_u$ .

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$ .

Input

The first line contains single integer $n$ $(1 ≤ n ≤ 2·105)$ .

The second line contains $n$ integers $a_1, a_2, ..., a_n$ $(1 ≤ a_i ≤ 10^9)$ — the integers written in the vertices.

The next $(n - 1)$ lines contain two integers each. The $i$ -th of these lines contains integers $p_i$ and $w_i$ $(1 ≤ p_i ≤ n, 1 ≤ w_i ≤ 10^9)$ — the parent of the $(i + 1)$ -th vertex in the tree and the number written on the edge between $p_i$ and $(i + 1)$ .

It is guaranteed that the given graph is a tree.

Output

Print $n$ integers — the $i$ -th of these numbers should be equal to the number of vertices that the $i$ -th vertex controls.

Examples

Input #1

Output #1

1 0 1 0 0

Input #2

Output #2

4 3 2 1 0

Notes

In the example test case the vertex 1 controls the vertex 3, the vertex 3 controls the vertex 5 (note that is doesn't mean the vertex 1 controls the vertex 5).

Solution

水题，很容易想到 $\Theta (N^2)$ 的想法，即两两枚举，显然超时。
考虑枚举一个点，去找控制它的点，从它的父亲开始找，一直往上……我们要找的是 $dist(i,j) ≤ a_i$ 的点。显然 j 不断往上， $dist(i,j)$ 单调递增。所以用二分或者树上倍增找就可以了。

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
const int maxn=200005,maxe=400005;
int n,tot=0,a[maxn],fa[maxn],sum[maxn],lnk[maxn],son[maxe],nxt[maxe],w[maxe];
long long dst[maxn];
bool vis[maxn];
vector <int> vec;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void add(int x,int y,int z){
    tot++;son[tot]=y;w[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline long long myabs(long long x){
    return x>0?x:-x;
}
inline void BuildDistance(int x){
    vis[x]=1;
    for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
        fa[son[i]]=x;
        dst[son[i]]=(long long)dst[x]+w[i];
        BuildDistance(son[i]);
    }
}
inline long long GetDistance(int x,int y){
    return myabs((long long)dst[x]-dst[y]);
}
inline void BuildSum(int x){
    vis[x]=1;
    int L=0,R=vec.size()-1,mid,now=-1;
    while (L<=R){
        mid=((R-L)>>1)+L;
        if ((long long)GetDistance(x,vec[mid])<=(long long)a[x]){
            now=mid;
            R=mid-1;
        } else L=mid+1;
    }
    if (now!=-1){
        now=vec[now];
        if (now!=x||GetDistance(x,now)<=a[x]) sum[fa[x]]++,sum[fa[now]]--;
    }
    vec.push_back(x);
    for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
        BuildSum(son[i]);
    }
    vec.erase(vec.end()-1);
}
inline void GetAnswer(int x){
    vis[x]=1;
    for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
        GetAnswer(son[i]);
        sum[x]+=sum[son[i]];
    }
}
int main(){
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=2;i<=n;i++){
        int x=read(),y=read();
        add(i,x,y);add(x,i,y);
    }
    BuildDistance(1);
    memset(vis,0,sizeof(vis));
    vec.clear();
    vec.push_back(1);
    BuildSum(1);
    memset(vis,0,sizeof(vis));
    GetAnswer(1);
    for (int i=1;i<=n;i++) printf("%d ",sum[i]);
    printf("\n");
    return 0;
}

SkyWT / 博客 / CodeForces 740D Alyona and a tree 题解：DFS + 二分