Gym 101147J Whistle's New Car（dfs）

题意：

有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+,sum[ret]-x[v])-sum;

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

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

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 using namespace std;

 typedef long long LL;

 typedef pair<int,LL> pll;

 const int maxn=+;

 int n;

 LL x[maxn];

 int vis[maxn];

 LL sum[maxn];

 int num[maxn];

 int cnt[maxn];

 int ret;

 vector<pll> G[maxn];

 void dfs(int u)

 {

     vis[u]=;

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

     {

         int v=G[u][i].first;

         int w=G[u][i].second;

         if(vis[v])  continue;

         sum[ret]=sum[ret-]+w;

         num[ret]=v;  //路径上第ret城市为v

         int pos=lower_bound(sum,sum+ret+,sum[ret]-x[v])-sum;//v出发能到达的最远的城市

         if(pos<ret)//如果能到达父结点城市

         {

             cnt[u]++; //父节点城市数量+1

             cnt[num[pos-]]--;  //这个一定要减，不然后面子节点的数加到父节点的时候，父节点就多加了

         }

         ret++;

         dfs(v);

         ret--;

         cnt[u]+=cnt[v];

     }

 }

 int main()

 {

    // freopen("car.in","r",stdin);

     //freopen("D:\\input.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         for(int i=;i<=n;i++)  G[i].clear();

         for(int i=;i<=n;i++)  scanf("%lld",&x[i]);

         for(int i=;i<n;i++)

         {

             int u,v;

             LL d;

             scanf("%d%d%lld",&u,&v,&d);

             G[u].push_back(make_pair(v,d));

             G[v].push_back(make_pair(u,d));

         }

         memset(vis,,sizeof(vis));

         memset(cnt,,sizeof(cnt));

         ret=;

         sum[]=;  //1~路径上第j个城市的距离和

         num[]=;

         dfs();    //从根结点出发遍历

         for(int i=;i<=n;i++)

             printf("%d%c",cnt[i],i!=n?' ':'\n');

     }

     return ;

 }

巴特西

Gym 101147J Whistle's New Car（dfs）

最新文章

热门文章