题目： 有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 a_i 的珠宝。你是一个珠宝商，现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。 在每次行程开始时，你手上有价
展开全文
看到大家都有牛币，我也想来骗点 我的解法： 题目给的是一颗有根树，每次查询的 u,v 又在一条从根出发的链上, 那就可以通过 dfs 把链剖成一个序列，这个序列是动态的，达到一个点 x：b[++tot] = a[x]，这个点的子树走完了：tot--; 设 dp[x] 为 b[1....x] 中从 x
展开全文
考察知识点：树上 DFS、倍增
本题很容易想到模拟的方式，但时间复杂度为 ，会超时。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
展开全文
Solution Code #pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N =
展开全文
Solution 题目中有两个关键信息： 1号节点是根节点。 节点 在节点 到根节点的最短路径上。 由于是树形结构，所以从 到 一定是不断地将 ，也就是 是 的祖先。 于是可以先进行一次 预处理出每个节点的父节点，之后回答询问。只有当某个节点的珠宝比手中的都值钱是才会采购，所以一
展开全文
思路一：树上倍增 //我们讲一讲这个是怎么逼近
//可以证明f[u][0]一定是f[father[u]][i]购买路径上的节点
//把一个查询作为一个节点。那么最后就是看从查询的u节点开始能最多跳多少次，并且不超过v节点。
//往上倍增寻找第一个比a[u]大的节点下面那个节点(他的父亲就是第一个比
展开全文
题目:给你一颗树,然后n个点,n-1条边.然后给你q组查询,每组查询给你三个数分别是:u,v,c 题目保证1是首都,并且u->v->1这种类型的查询.问你从u->v的最长上升子序列长度..接下来我来解说下题解吧,hhh,因为我不会,tcl..给题解增添细节;题解的思路是 类似rmq
展开全文
题目链接：https://ac.nowcoder.com/acm/problem/13331来份在线查询的代码，先说这道题，在第一遍dfs求重儿子的时候，顺便处理数组dp[maxn]，其中dp[u]为从节点u到根节点1有几次购买操作，如何求答案呢？ 假设有两个点x和y，其中y----是x的某一级祖先
展开全文
题目相信大家都看的懂思路：我们从几个点入手，剖析出这题的解题思路。首先这是个树状网络，那么我们肯定可以从树的思路入手。然后很重要的一点，，保证 v 在 u 前往首都的最短路径上。那么很明显，v就是在u和根节点的路径上的一点。那么就可以归到求LCA的问题了。普通的往上跑，那么这题的数据范围会超时，所以
展开全文
NC13331 城市网络 题目地址： https://ac.nowcoder.com/acm/problem/13331 基本思路： 由于数据更新我们的旧解法已经完美的TLE了; 所以新的思路肯定不能暴力了,我们还是抓住保证 v 在 u 前往首都的最短路径上这句话,使用倍增优化; 不理解倍增的
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
