首页 > 试题广场 >

城市网络

[编程题]城市网络

热度指数：113 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 a_i 的珠宝。
你是一个珠宝商，现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。在每次行程开始时，你手上有价值为 c 的珠宝（每次行程可能不同），并且每经过一个城市时（包括 u 和 v ），假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。
现在你想要对每一次行程，求出会进行多少次购买事件。

输入描述:

第一行，两个正整数 n , q (2 ≤ n ≤ 10^5 , 1 ≤ q ≤ 10^5)。
第二行，n 个正整数 a_i (1 ≤ a_i ≤ 10^5) 描述每个城市售卖的珠宝的价值。
接下来 n-1 行，每行描述一条道路 x , y (1 ≤ x,y ≤ n)，表示有一条连接 x 和 y 的道路。
接下来 q 行，每行描述一次行程 u , v , c (1 ≤ u,v ≤ n , 1 ≤ c ≤ 10^5)。

输出描述:

对于每次行程输出一行，为所购买次数。

示例1

输入

输出

算法知识视频讲解

rk_no

发表于 2020-03-30 14:56:34

题目：有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 a_i 的珠宝。你是一个珠宝商，现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。在每次行程开始时，你手上有价展开全文

KobeDuu

发表于 2020-03-30 23:20:38

看到大家都有牛币，我也想来骗点我的解法：题目给的是一颗有根树，每次查询的 u,v 又在一条从根出发的链上, 那就可以通过 dfs 把链剖成一个序列，这个序列是动态的，达到一个点 x：b[++tot] = a[x]，这个点的子树走完了：tot--; 设 dp[x] 为 b[1....x] 中从 x 展开全文

小嗷犬

发表于 2023-08-19 01:30:25

考察知识点：树上 DFS、倍增本题很容易想到模拟的方式，但时间复杂度为，会超时。 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; 展开全文

Kur1su

发表于 2020-03-30 22:44:16

Solution Code #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long long LL; const int N = 展开全文

LB_tq

发表于 2020-03-30 11:15:12

Solution 题目中有两个关键信息： 1号节点是根节点。节点在节点到根节点的最短路径上。由于是树形结构，所以从到一定是不断地将，也就是是的祖先。于是可以先进行一次预处理出每个节点的父节点，之后回答询问。只有当某个节点的珠宝比手中的都值钱是才会采购，所以一展开全文

工大最菜

发表于 2020-03-30 23:22:20

思路一：树上倍增 //我们讲一讲这个是怎么逼近 //可以证明f[u][0]一定是f[father[u]][i]购买路径上的节点 //把一个查询作为一个节点。那么最后就是看从查询的u节点开始能最多跳多少次，并且不超过v节点。 //往上倍增寻找第一个比a[u]大的节点下面那个节点(他的父亲就是第一个比展开全文

shyyhs

发表于 2020-04-02 02:15:10

题目:给你一颗树,然后n个点,n-1条边.然后给你q组查询,每组查询给你三个数分别是:u,v,c 题目保证1是首都,并且u->v->1这种类型的查询.问你从u->v的最长上升子序列长度..接下来我来解说下题解吧,hhh,因为我不会,tcl..给题解增添细节;题解的思路是类似rmq 展开全文

fuzhiji

发表于 2020-04-08 22:18:28

题目链接：https://ac.nowcoder.com/acm/problem/13331来份在线查询的代码，先说这道题，在第一遍dfs求重儿子的时候，顺便处理数组dp[maxn]，其中dp[u]为从节点u到根节点1有几次购买操作，如何求答案呢？假设有两个点x和y，其中y----是x的某一级祖先展开全文

levil

发表于 2020-03-31 09:09:20

题目相信大家都看的懂思路：我们从几个点入手，剖析出这题的解题思路。首先这是个树状网络，那么我们肯定可以从树的思路入手。然后很重要的一点，，保证 v 在 u 前往首都的最短路径上。那么很明显，v就是在u和根节点的路径上的一点。那么就可以归到求LCA的问题了。普通的往上跑，那么这题的数据范围会超时，所以展开全文

sunsetcolors

发表于 2020-03-30 13:09:35

NC13331 城市网络题目地址： https://ac.nowcoder.com/acm/problem/13331 基本思路：由于数据更新我们的旧解法已经完美的TLE了; 所以新的思路肯定不能暴力了,我们还是抓住保证 v 在 u 前往首都的最短路径上这句话,使用倍增优化; 不理解倍增的展开全文

问题信息

C++工程师 golang工程师 2017 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师 c#工程师美团测试开发工程师大数据开发工程师 Java工程师

来自：CodeM 2017美...

难度：

0条回答 4收藏 2369浏览

通过挑战的用户

Reedaaaa

2021-04-12 20:43:25
Ultsweet

2020-02-15 11:57:45
明天也不想努力

2019-11-07 15:13:20
Insolub...

2019-11-04 20:42:16

城市网络

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题