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