SkyWT

7/24/2018

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

This blog post is only available in Simplified Chinse.

题目链接 vector 真的好用~

Problem

Alyona has a tree with nn vertices. The root of the tree is the vertex 1. In each vertex Alyona wrote an positive integer, in the vertex ii she wrote aia_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)dist(v, u) as the sum of the integers written on the edges of the simple path from vv to uu.

The vertex vv controls the vertex uu (vu)(v ≠ u) if and only if uu is in the subtree of vv and dist(v,u)audist(v, u) ≤ a_u.

Alyona wants to settle in some vertex. In order to do this, she wants to know for each vertex vv what is the number of vertices uu such that vv controls uu.

Input

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

The second line contains nn integers a1,a2,...,ana_1, a_2, ..., a_n (1ai109)(1 ≤ a_i ≤ 10^9) — the integers written in the vertices.

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

It is guaranteed that the given graph is a tree.

Output

Print nn integers — the ii-th of these numbers should be equal to the number of vertices that the ii-th vertex controls.

Examples

Input #1

5
2 5 1 4 6
1 7
1 1
3 5
3 6

Output #1

1 0 1 0 0

Input #2

5
9 7 8 6 5
1 1
2 1
3 1
4 1

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

水题,很容易想到 Θ(N2)\Theta (N^2) 的想法,即两两枚举,显然超时。 考虑枚举一个点,去找控制它的点,从它的父亲开始找,一直往上……我们要找的是 dist(i,j)aidist(i,j) ≤ a_i 的点。显然 j 不断往上,dist(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;
}

Post a New Comment

Please login to leave a comment.