Gym 101147J Whistle's New Car（dfs）-白红宇

Gym 101147J Whistle's New Car（dfs）

阅读量：4649 次

发布时间：2019-06-09

本文共 915 字，大约阅读时间需要 3 分钟。

题意：

有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
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             10 using namespace std;11 typedef long long LL;12 typedef pair
              
                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
               
                 G[maxn];23 24 25 void dfs(int u)26 {27 vis[u]=1;28 for(int i=0;i

转载于:https://www.cnblogs.com/zyb993963526/p/6908994.html

你可能感兴趣的文章