D. Alyona and a tree（二分 + 树上差分）

98 阅读 0 评论 65 点赞

我是靠谱客的博主有魅力百褶裙，最近开发中收集的这篇文章主要介绍D. Alyona and a tree（二分 + 树上差分），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接
题意
一棵树，树上有 $n$ 个点，标号为1~n，且1是树根。然后每个点都有一个值 $a [i]$ ，每条边也有一个权值 $w$ ，然后让你输出每个可以控制点的数目。（比如 $u$ 控制 $v$ ，即树上 $u - > v$ 的权值 $d [u, v] < = a [v]$ ）
思路
首先比较好想的是暴力的方法。
预处理深度遍历树根到所有节点的权值，然后对每个点进行 $d f s$ ，结果T。
我们在脑海中想象下遍历这棵树的过程，在DFS过程中在栈中总会呈现一条树根到子节点的路径，我们在这条路径上进行二分查找这条路径上满足条件的距当前节点最远点（也就是最靠根的节点），然后这一段路径区间都可以加1，区间修改，我们可以差分来缩减时间复杂度，只不过这是在树上差分。
有一点需要注意，差分时注意区间首尾别颠倒！
$A C C o d e :$

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
const ll N = 2e5+10;
ll d[N];//到根节点的距离
ll a[N];
int head[N],tot;
struct Edge{
   int next;
   int to;
   ll dis;
}edge[N<<2];
inline void add(int from,int to,ll dis){
   edge[++tot].next = head[from];
   edge[tot].to = to;
   edge[tot].dis = dis;
   head[from] = tot;
}
vector<int> T;//记录路径
int c[N];//答案数组
int pre[N];//记录前驱
void dfs(int root){
	int l = 0,r = T.size() - 1;
	while(l < r){
		int mid = l + r >> 1;
		if(d[root] - d[T[mid]] <= a[root]) r = mid;
		else l = mid + 1;
	}
	if(T.size() != 0&&d[root] - d[T[r]] <= a[root]){
		c[pre[root]] ++;
		c[pre[T[r]]] --;
	}
	T.push_back(root);
	for(int i = head[root];~i;i = edge[i].next){
		int  y = edge[i].to;
		ll dis = edge[i].dis;
		d[y] = d[root] + dis;
		dfs(y);
	}
	T.pop_back();
}
void DFS(int x){
	for(int i = head[x];~i;i = edge[i].next){
		int y = edge[i].to;
		DFS(y);
		c[x] += c[y];
		
	}
}
int main(){
   memset(head,-1,sizeof head);
   int n;
   scanf("%d",&n);
   for(int i = 1;i <= n;++i) scanf("%lld",&a[i]);
   int u;ll dis;
   for(int i = 2;i <= n;++i){
      scanf("%d%lld",&u,&dis);
      add(u,i,dis);
	  pre[i] = u;
      //add(i,u,dis);
   }
   dfs(1);
   DFS(1);
   for(int i = 1;i <= n;++i) cout<<c[i]<<' ';

}