codeforces 739B B. Alyona and a tree

71 阅读 0 评论 47 点赞

我是靠谱客的博主专注鱼，最近开发中收集的这篇文章主要介绍codeforces 739B B. Alyona and a tree，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这个题目想了好久都没有想出好的方法，最终看了别人的思路解决的。写一篇博客纪念一下做这个题的想法和学到的一些新东西。读这个题的时候以为会是dp，仔细想了想，又不太符合dp的特征。然后，就按照数据结构的想法思考，想了好久，还是没什么思路，而且用队列，从叶子节点模拟了一发，以为可以过。提交的时候才想起来，肯定会TLE呀，结果果断TLE，想想也是醉了。最后想着想着，觉得时间复杂度怎么也应该时n*lgn才能过。于是，开始思考，如何能在lg（n）的时间复杂度内，解决一个节点的对所有节点的贡献。于是，想利用前缀和，看一下能不能二分，求出范围。这样，又有新的问题，从树根开始求前缀和的话，并不难。但是，自己怎么想都是应该求的是子节点到父节点的前缀和；第二个问题是即使求出了前缀和，找出了节点所影响的范围，但是怎么去更新这个范围尼。直接更新的话，不还是会超时。最后，选者了放弃。看了别人的想法。真是感慨自己的智商呀。对于第一个问题：将dist(v, u ) <= a[u]可以看成是dep[u]（前缀和） - dep[v] <= a[u]，可以转化为 dep[u]-a[u] <= dep[v]；这样就可以二分找v的范围了。对于第二个问题：其实我们没有必要去一个一个的更新范围内的值，只需要定义前缀即可，若当前节点的值为1，则表示当前节点到树根的路径上每个节点均加1，那么对于要更新一个范围，只需要在尾部的位置加1，首部之前的位置减1即可，然后dfs求结果。最后，注意要用__int64。代码如下：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define ll __int64

using namespace std;

const int MAX = 200010;

ll a[MAX], p[MAX], d[MAX], res[MAX], pre[MAX], path[MAX];
vector<int>G[MAX];

void solve(int root, int c, ll s){
	path[c] = root;
	pre[c] = s;

	if (c > 1){

		int l = 1, r = c;

		while (l < r){
			int mid = (l + r) / 2;

			if (s-a[root] <= pre[mid]){
				r = mid;
			}else{
				l = mid + 1;
			}
		}

		res[p[root]] += 1;
		res[path[r-1]] -= 1;
	}

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

		solve(u, c+1, s+d[u]);
	}
}

ll ans[MAX];

void dfs(int root){

	ans[root] = res[root];

	for (int i = 0; i<G[root].size(); i++){
		int u = G[root][i];
		dfs(u);
		ans[root] += ans[u];
	}

}



int main(int argc, char const *argv[])
{
	/* code */

	int n;
	while (scanf("%d", &n) != EOF){
		for (int i=1; i<=n; i++){
			scanf("%I64d", &a[i]);
		}

		memset(res, 0, sizeof(res));
		for (int i=0; i<MAX; i++) G[i].clear();

		p[1] = 0;
		for (int i = 2; i<=n; i++){
			scanf("%I64d%I64d", &p[i], &d[i]);
			G[p[i]].push_back(i);
		}

		solve(1, 1, 0);
		dfs(1);

		printf("%I64d", ans[1]);
		for (int i = 2; i<=n; i++){
			printf(" %I64d", ans[i]);
		}
		printf("n");
	}


	return 0;
}