DFS

题目链接 Whistle's New Car

题目的意思是给定 n 个城市编号 1-n ,每个城市都有一个权值 $X_i$
,两个城市间的距离 $C_ {ij}$ 这些城市的结构是一颗以 1 为根节点的树，输出每个城市i的attractiveness ，每个节点 attractiveness 是满足以下条件的城市的个数

1. j 是 i 的子树。
2. 在城市j加满 $X_j$ 的油后不再加油能到达 i 城市。

主要思路：从根节点1出发DFS整棵树，我们用s[i]表示根节点到第i个节点的路径长度之和,(第 i 个节点貌似不恰当，可以理解为第 i 层).num 数组保存了我们 dfs 过程中之前所经过的城市(后面有用)。对于当前城市i它只能往上走，我们需要判断它能往上走到哪里,我们可以发现,对于在i之前的城市j如果满足 s[j]+x[i]>=s[i] ，那么我们就可以从城市i走到城市j，因此我们需要找到最小的j，满足 s[j]>=s[i]-x[i] ,对于这个我们可以二分查找s数组，找到满足条件的最小的j,j城市满足条件，j到i路上所有的城市节点都满足条件(不包括i)，因此我们把j,j+1....i-1这些城市答案都加1，对于闭区间[j~i-1] 的值加上1，可以类似于差分来处理，cnt[i-1]++,cnt[j-1]--.这里让cnt[j-1]--，是为消除城市节点j之前的城市的影响，因为我们每次统计答案是cnt[u] += cnt[v] (v是u的孩子),对[j~i-1]之间的城市我们这样操作后它们的答案都会加1，但j之前的城市我们不能让它答案加1，因此我们cnt[j-1]--来消除这个影响。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
const int N = 5e5 + 10;
int n;
ll a[N],s[N];
typedef pair<int, ll> P;
vector<P> p[N];
int cnt[N],num[N];
int ret;
void dfs(int u, int pre)
{
	for (auto E : p[u])
	{
		int v = E.first;
		ll w = E.second;
		if (v == pre) continue;
		s[ret] = s[ret - 1] + w;
		num[ret] = v; //路径上第ret城市为v
		int pos = lower_bound(s, s + ret + 1, s[ret] - a[v])-s;
		if (pos < ret)//如果能到达父结点城市
		{
			cnt[u]++;
			if (pos) cnt[num[pos - 1]]--;//这个一定要减，不然后面节点的数加到父节点的时候，父节点就多加了
		}
		ret++;
		dfs(v, u);
		ret--;
		cnt[u] += cnt[v];
	}
}
int main()
{
	freopen("car.in", "r", stdin);
	int T;
	scanf("%d", &T);
	while (T--)
	{
		ret = 1;
		memset(cnt, 0, sizeof(cnt));
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			scanf("%lld", &a[i]);
			p[i].clear();
		}
		for (int i = 1; i < n; i++)
		{
			int u,v;
			ll w;
			scanf("%d%d%lld", &u, &v, &w);
			p[u].push_back(P(v, w));
			p[v].push_back(P(u, w));
		}
		ret = 1;
		num[0] = 1;
		s[0] = 0;
		dfs(1, -1);
		for (int i = 1; i <= n; i++)
			printf("%d%c", cnt[i], i == n ? '\n' : ' ');
	}
	fclose(stdin);
	return 0;
}