Gym 101147J Whistle's New Car（dfs）

https://vjudge.net/problem/Gym-101147J

题意：

有n个城市，每个城市有一个权值，表示在这个城市的加油站可以加多少油。

现在要计算每个城市i，有多少个城市j可以到达它：

① j 是 i 的子树。

② 在城市 j 加满Xj的油后不再加油能到达 i 城市。

思路：
我们从根结点出发，dfs整棵树，在dfs的过程中，我们维护一个道路长度的和sum[]，sum[j]就是1到第j个城市的路径之和。

假如我们现在dfs到了第j个城市v，此时1~j的路径之和就是sum[j],然后sum[j]-x[v]就是从v城市出发所能到达的最远距离。

int pos=lower_bound(sum,sum+ret+1,sum[ret]-x[v])-sum;

接下来二分查找计算出从v出发在这条路径上所能到达的最远的城市。它所能到达的城市都需要+1。

最后把子节点的个数加到父节点上即可。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 using namespace std;
11 typedef long long LL;
12 typedef pair<int,LL> pll;
13 const int maxn=500000+5;
14 
15 int n;
16 LL x[maxn];
17 int vis[maxn];
18 LL sum[maxn];
19 int num[maxn];
20 int cnt[maxn];
21 int ret;
22 vector<pll> G[maxn];
23 
24 
25 void dfs(int u)
26 {
27     vis[u]=1;
28     for(int i=0;i<G[u].size();i++)
29     {
30         int v=G[u][i].first;
31         int w=G[u][i].second;
32         if(vis[v])  continue;
33         sum[ret]=sum[ret-1]+w;
34         num[ret]=v;  //路径上第ret城市为v
35         int pos=lower_bound(sum,sum+ret+1,sum[ret]-x[v])-sum;//v出发能到达的最远的城市
36         if(pos<ret)//如果能到达父结点城市
37         {
38             cnt[u]++; //父节点城市数量+1
39             cnt[num[pos-1]]--;  //这个一定要减，不然后面子节点的数加到父节点的时候，父节点就多加了
40         }
41         ret++;
42         dfs(v);
43         ret--;
44         cnt[u]+=cnt[v];
45     }
46 }
47 
48 
49 int main()
50 {
51    // freopen("car.in","r",stdin);
52     //freopen("D:\input.txt","r",stdin);
53     int T;
54     scanf("%d",&T);
55     while(T--)
56     {
57         scanf("%d",&n);
58         for(int i=0;i<=n;i++)  G[i].clear();
59         for(int i=1;i<=n;i++)  scanf("%lld",&x[i]);
60         for(int i=1;i<n;i++)
61         {
62             int u,v;
63             LL d;
64             scanf("%d%d%lld",&u,&v,&d);
65             G[u].push_back(make_pair(v,d));
66             G[v].push_back(make_pair(u,d));
67         }
68         memset(vis,0,sizeof(vis));
69         memset(cnt,0,sizeof(cnt));
70         ret=1;
71         sum[0]=0;  //1~路径上第j个城市的距离和
72         num[0]=1;
73         dfs(1);    //从根结点出发遍历
74         for(int i=1;i<=n;i++)
75             printf("%d%c",cnt[i],i!=n?' ':'
');
76     }
77     return 0;
78 }