写在最前面

个人认为这次考试的时间安排比较合理:花 \(30min\) 写完暴力思考第一题无果后开始写第二题,花费 \(90min\) 写完调完,并且写了另一份暴力和数据生成器,完整对拍过,第三题写了暴力,第四题试图读懂题意无果后猜了 \(2\) 的结论。

万松园

题目描述

题目描述

万松园地处繁华。其南临武广,东倚中山公园的得天独厚的位置,让生活在其中的人们习惯于四处游玩。然而 \(2019\) 年底疫情的到来,政府不得不采取封控的措施,以抵制疫情的蔓延。但这与万松园居民的习惯背道而驰,直接推行阻力太大。疫情才刚刚开始,卫健委正考虑一种折中的措施:

具体而言,万松园可以看作一颗树,树上有 \(n\) 个节点。调查显示,不同的路径有不同的“受欢迎程度”,一个道路的受欢迎程度越小,其封控的成本越低。由于封控就是让一个人与尽量少的其他人接触,只要将这棵树划分为一些较小的连通块就可以较为轻松地达到封控的目的。现在你要为卫健委写一个程序,支持查询当封控所有“受欢迎程度”低于 \(K\) 的道路时,点 \(v\) 能到达的其他节点数量。

输入格式

第一行输入两个正整数 \(n,q(1≤n,q≤10^5)\),表示图中节点的个数和查询的次数。

之后 \(n-1\) 行,每行三个整数 \(u,v,w\),表示有一条 \(u,v\) 间的路径,“受欢迎程度”为 \(w(1≤u,v≤n,1≤w≤10^9)\)

之后 \(q\) 行描述了卫健委的 \(q\) 次查询。每行输入两个整数 \(k_i,v_i\),表示当 \(K=k_i\) 时,查询点 \(v_i\) 能到达的其他节点数量。\((1≤k_i≤10^9,1≤v_i≤n)\)

输出格式

输出共 \(q\) 行,对于每次查询,输出一行一个整数表示答案。

提示

对于 \(10\%\) 的数据,\(1≤n,q≤5\)

对于 \(30\%\) 的数据,\(1≤n,q≤1000\)

对于 \(100\%\) 的数据,\(1≤n,q≤10^5,1≤u,v≤n,1≤w≤10^9,1≤k_i≤10^9,1≤v_i≤n\)

Solution

  • 考虑把询问离线。

原文地址:http://www.cnblogs.com/Star-LIcsAy/p/16794210.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性