#DFS序+二分+前缀和# Codeforces Round #381 (Div. 1) B. Alyona and a tree

63 阅读 0 评论 42 点赞

我是靠谱客的博主漂亮手机，最近开发中收集的这篇文章主要介绍#DFS序+二分+前缀和# Codeforces Round #381 (Div. 1) B. Alyona and a tree，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

B. Alyona and a tree

time limit per test 2 seconds

memory limit per test 256 megabytes

input standard input

output standard output

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 vcontrols u.

Input

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.

Output

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

Description：

给出一颗由n个节点构成的带权树，求每个节点可以控制的节点数，v节点控制 u 节点的条件：dist(v, u) <= a[u]。

Solution：

假设 dis[x] 表示根节点到 x 节点上的边权和，则 x 这个节点被 u 节点控制的条件为：dis[x] - dis[u] <= a[x]，即 dis[x] - a[x] <= dis[u]。由于 dis数组是通过DFS序来维护的，所以一定是单调递增的，那么就可以利用二分找出dis数组中第一个满足 dis[x] - a[x] <= dis[u] 的u节点，那么 u → x 的路径上的所有节点都能够控制 x 节点，而 u 节点以上的节点都不能控制x节点，所以在这里可以引入一个利用前缀和记录答案的思想：假设在当前已找到一条路径为 u → x ，其中 u 节点的父节点为 fa[u]，x节点的父节点为 fa[x]，那么令 ans[fa[x]]++，ans[fa[u]]--（ans[fa[x]]++这一语句可以使用另一种记录方法：将 ans 数组在一开始时就赋值为1，然后再最后答案处都减一也可），然后在DFS序的时候累加答案记录前缀和即可。

Implementation：

DFS序维护 dis数组和记录 ans数组的前缀和

二分查找每个节点的合法路径

前缀和（或者是树上差分思想）维护答案

Code：

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define Fio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fopen freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
#define mst(a, b) memset(a, b, sizeof(a))
#define _rush() int T; cin >> T; while(T--)
#define rush() int T; scanf("%d", &T); while(T--)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;
const int Mod = 1e9 + 7;
const int MaxN = 2e5 + 5;

vector <PIL> G[MaxN];
vector <PLI> path;
LL a[MaxN], dis[MaxN];
int vis[MaxN], ans[MaxN];

void DFS(int x, int fa) {
	vis[x] = 1;
	//ans[x]++;  //选择在一开始时将ans数组赋值1
	int pos = lower_bound(path.begin(), path.end(), PLI(dis[x] - a[x], 0)) - path.begin(); //二分查找第一个合法u节点
	if(--pos >= 0) ans[path[pos].second]--; //u节点的父节点（第一个不合法的节点）减一
	ans[fa]++; //（如果使用一开始将ans赋值为1，不需要这句）当前查找节点的父节点加一，u —> fa这些节点都可控制当前节点，所以答案加一
	path.push_back(PLI(dis[x], x)); //当前路径压入查找路径中
	for(int i = 0; i < G[x].size(); i++) {
		int u = G[x][i].first; LL w = G[x][i].second;
		if(vis[u]) continue;
		dis[u] = dis[x] + w;
		DFS(u, x);
		ans[x] += ans[u]; //前缀和维护答案
	}
	path.pop_back(); //维护查找路径的根节点
}

int main()
{
    Fio;

	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 2; i <= n; i++) {
		int u; LL d;
		cin >> u >> d;
		G[i].push_back(PIL(u, d));
		G[u].push_back(PIL(i, d));
	}
	DFS(1, 0);
	//for(int i = 1; i <= n; i++) cout << ans[i] - 1 << " ";
	for(int i = 1; i <= n; i++) cout << ans[i] << " ";
	cout << endl;
	return 0;
}